Contextual Bandits with Similarity Information

Introduction

In a multi-armed bandit problem (henceforth, “multi-armed bandit” will be abbreviated as MAB), an algorithm is presented with a sequence of trials. In each round, the algorithm chooses one alternative from a set of alternatives (arms) based on the past history, and receives the payoff associated with this alternative. The goal is to maximize the total payoff of the chosen arms. The MAB setting has been introduced in 1952 in Robbins 1952 and studied intensively since then in Operations Research, Economics and Computer Science. This setting is a clean model for the exploration-exploitation trade-off, a crucial issue in sequential decision-making under uncertainty.

One standard way to evaluate the performance of a bandit algorithm is regret, defined as the difference between the expected payoff of an optimal arm and that of the algorithm. By now the MAB problem with a small finite set of arms is quite well understood, e.g. see Lai and Robbins 1985, Auer et al. 2002b, Auer et al. 2002a. However, if the arms set is exponentially or infinitely large, the problem becomes intractable unless we make further assumptions about the problem instance. Essentially, a bandit algorithm needs to find a needle in a haystack; for each algorithm there are inputs on which it performs as badly as random guessing.

Bandit problems with large sets of arms have been an active area of investigation in the past decade (see Section 2 for a discussion of related literature). A common theme in these works is to assume a certain structure on payoff functions. Assumptions of this type are natural in many applications, and often lead to efficient learning algorithms (Kleinberg 2005). In particular, a line of work started in Agrawal 1995 assumes that some information on similarity between arms is available.

In this paper we consider similarity information in the setting of contextual bandits (Woodroofe 1979, Auer 2002, Wang et al. 2005, Pandey et al. 2007, Langford and Zhang 2007), a natural extension of the basic MAB problem where before each round an algorithm is given the context – a hint about the payoffs in this round. Contextual bandits are directly motivated by the problem of placing advertisements on webpages, one of the crucial problems in sponsored search. One can cast it as a bandit problem so that arms correspond to the possible ads, and payoffs correspond to the user clicks. Then the context consists of information about the page, and perhaps the user this page is served to. Furthermore, we assume that similarity information is available on both the context and the arms. Following the work in Agrawal 1995, Kleinberg 2004, Auer et al. 2007, Kleinberg et al. 2008b on the (non-contextual) bandits, a particularly simple way to represent similarity information in the contextual bandit setting is via a similarity distance between the context-arm pairs, which gives an upper bound on the difference between the corresponding payoffs.

The contextual bandits framework is defined as follows. Let $X$ be the context set and $Y$ be the arms set, and let $\mathcal{P}\subset X\times Y$ be the set of feasible context-arms pairs. In each round $t$, the following events happen in succession:

a context $x_{t}\in X$ is revealed to the algorithm,

the algorithm chooses an arm $y_{t}\in Y$ such that $(x_{t},y_{t})\in\mathcal{P}$,

payoff (reward) $\pi_{t}\in$ is revealed.

In general, the goal of a bandit algorithm is to maximize the total payoff $\sum_{t=1}^{T}\pi_{t}$, where $T$ is the time horizon. In the contextual MAB setting, we benchmark the algorithm’s performance in terms of the context-specific “best arm”. Specifically, the goal is to minimize the contextual regret:

The context-specific best arm is a more demanding benchmark than the best arm used in the “standard” (context-free) definition of regret.

The similarity information is given to an algorithm as a metric space $(\mathcal{P},\mathcal{D})$ which we call the similarity space, such that the following Lipschitz condition In other words, $\mu$ is a Lipschitz-continuous function on $(X,\mathcal{P})$, with Lipschitz constant $K_{\text{Lip}}=1$. Assuming $K_{\text{Lip}}=1$ is without loss of generality (as long as $K_{\text{Lip}}$ is known to the algorithm), since we can re-define $\mathcal{D}\leftarrow K_{\text{Lip}}\,D$. holds:

Without loss of generality, $\mathcal{D}\leq 1$. The absence of similarity information is modeled as $\mathcal{D}=1$.

An instructive special case is the product similarity space $(\mathcal{P},\mathcal{D})=(X\times Y,\mathcal{D})$, where $(X,\mathcal{D}_{\text{X}})$ is a metric space on contexts (context space), and $(Y,\mathcal{D}_{\text{Y}})$ is a metric space on arms (arms space), and

Prior work: uniform partitions.

Hazan and Megiddo 2007 consider contextual MAB with similarity information on contexts. They suggest an algorithm that chooses a “uniform” partition $S_{\text{X}}$ of the context space and approximates $x_{t}$ by the closest point in $S_{\text{X}}$, call it $x^{\prime}_{t}$. Specifically, the algorithm creates an instance $\mathcal{A}(x)$ of some bandit algorithm $\mathcal{A}$ for each point $x\in S_{\text{X}}$, and invokes $\mathcal{A}(x^{\prime}_{t})$ in each round $t$. The granularity of the partition is adjusted to the time horizon, the context space, and the black-box regret guarantee for $\mathcal{A}$. Furthermore, Kleinberg 2004 provides a bandit algorithm $\mathcal{A}$ for the adversarial MAB problem on a metric space that has a similar flavor: pick a “uniform” partition $S_{\text{Y}}$ of the arms space, and run a $k$-arm bandit algorithm such as exp3 Auer et al. 2002b on the points in $S_{\text{Y}}$. Again, the granularity of the partition is adjusted to the time horizon, the arms space, and the black-box regret guarantee for exp3.

Applying these two ideas to our setting (with the product similarity space) gives a simple algorithm which we call the uniform algorithm. Its contextual regret, even for adversarial payoffs, is

where $d_{\text{X}}$ is the covering dimension of the context space and $d_{\text{Y}}$ is that of the arms space.

Our contributions.

Using “uniform” partitions disregards the potentially benign structure of expected payoffs and context arrivals. The central topic in this paper is adaptive partitions of the similarity space which are adjusted to frequently occurring contexts and high-paying arms, so that the algorithms can take advantage of the problem instances in which the expected payoffs or the context arrivals are “benign” (“low-dimensional”), in a sense that we make precise later.

We present two main results, one for stochastic payoffs and one for adversarial payoffs. For stochastic payoffs, we provide an algorithm called contextual zooming which “zooms in” on the regions of the context space that correspond to frequently occurring contexts, and the regions of the arms space that correspond to high-paying arms. Unlike the algorithms in prior work, this algorithm considers the context space and the arms space jointly – it maintains a partition of the similarity space, rather than one partition for contexts and another for arms. We develop provable guarantees that capture the “benign-ness” of the context arrivals and the expected payoffs. In the worst case, we match the guarantee (3) for the uniform algorithm. We obtain nearly matching lower bounds using the KL-divergence technique from (Auer et al. 2002b, Kleinberg 2004). The lower bound is very general as it holds for every given (product) similarity space and for every fixed value of the upper bound.

Our stochastic contextual MAB setting, and specifically the contextual zooming algorithm, can be fruitfully applied beyond the ad placement scenario described above and beyond MAB with similarity information per se. First, writing $x_{t}=t$ one can incorporate “temporal constraints” (across time, for each arm), and combine them with “spatial constraints” (across arms, for each time). The analysis of contextual zooming yields concrete, meaningful bounds this scenario. In particular, we recover one of the main results in Slivkins and Upfal 2008. Second, our setting subsumes the stochastic sleeping bandits problem Kleinberg et al. 2008a, where in each round some arms are “asleep”, i.e. not available in this round. Here contexts correspond to subsets of arms that are “awake”. Contextual zooming recovers and generalizes the corresponding result in Kleinberg et al. 2008a. Third, following the publication of a preliminary version of this paper, contextual zooming has been applied to bandit learning-to-rank in Slivkins et al. 2013.

For the adversarial setting, we provide an algorithm which maintains an adaptive partition of the context space and thus takes advantage of “benign” context arrivals. We develop provable guarantees that capture this “benign-ness”. In the worst case, the contextual regret is bounded in terms of the covering dimension of the context space, matching (3). Our algorithm is in fact a meta-algorithm: given an adversarial bandit algorithm Bandit, we present a contextual bandit algorithm which calls Bandit as a subroutine. Our setup is flexible: depending on what additional constraints are known about the adversarial payoffs, one can plug in a bandit algorithm from the prior work on the corresponding version of adversarial MAB, so that the regret bound for Bandit plugs into the overall regret bound.

Discussion.

Adaptive partitions (of the arms space) for context-free MAB with similarity information have been introduced in (Kleinberg et al. 2008b, Bubeck et al. 2011a). This paper further explores the potential of the zooming technique in (Kleinberg et al. 2008b). Specifically, contextual zooming extends this technique to adaptive partitions of the entire similarity space, which necessitates a technically different algorithm and a more delicate analysis. We obtain a clean algorithm for contextual MAB with improved (and nearly optimal) bounds. Moreover, this algorithm applies to several other, seemingly unrelated problems and unifies some results from prior work.

One alternative approach is to maintain a partition of the context space, and run a separate instance of the zooming algorithm from Kleinberg et al. 2008b on each set in this partition. Fleshing out this idea leads to the meta-algorithm that we present for adversarial payoffs (with Bandit being the zooming algorithm). This meta-algorithm is parameterized (and constrained) by a specific a priori regret bound for Bandit. Unfortunately, any a priori regret bound for zooming algorithm would be a pessimistic one, which negates its main strength – the ability to adapt to “benign” expected payoffs.

Map of the paper.

Section 2 is related work, and Section 3 is Preliminaries. Contextual zooming is presented in Section 4. Lower bounds are in Section 5. Some applications of contextual zooming are discussed in Section 6. The adversarial setting is treated in Section 8.

Related work

A proper discussion of the literature on bandit problems is beyond the scope of this paper. This paper follows the line of work on regret-minimizing bandits; a reader is encouraged to refer to (Cesa-Bianchi and Lugosi 2006, Bubeck and Cesa-Bianchi 2012) for background. A different (Bayesian) perspective on bandit problems can be found in (Gittins et al. 2011).

Most relevant to this paper is the work on bandits with large sets of arms, specifically bandits with similarity information (Agrawal 1995, Kleinberg 2004, Auer et al. 2007, Pandey et al. 2007, Kocsis and Szepesvari 2006, Munos and Coquelin 2007, Kleinberg et al. 2008b, Bubeck et al. 2011a, Kleinberg and Slivkins 2010, Maillard and Munos 2010). Another commonly assumed structure is linear or convex payoffs, e.g. (Awerbuch and Kleinberg 2008, Flaxman et al. 2005, Dani et al. 2007, Abernethy et al. 2008, Hazan and Kale 2009, Bubeck et al. 2012). Linear/convex payoffs is a much stronger assumption than similarity, essentially because it allows to make strong inferences about far-away arms. Other assumptions have been considered, e.g. (Wang et al. 2008, Bubeck and Munos 2010). The distinction between stochastic and adversarial payoffs is orthogonal to the structural assumption (such as Lipschitz-continuity or linearity). Papers on MAB with linear/convex payoffs typically allow adversarial payoffs, whereas papers on MAB with similarity information focus on stochastic payoffs, with notable exceptions of Kleinberg 2004 and Maillard and Munos 2010.

The notion of structured adversarial payoffs in this paper is less restrictive than the one in Maillard and Munos 2010 (which in turn specializes the notion from linear/convex payoffs), in the sense that the Lipschitz condition is assumed on the expected payoffs rather than on realized payoffs. This is a non-trivial distinction, essentially because our notion generalizes stochastic payoffs whereas the other one does not.

In (Auer 2002) and (Chu et al. 2011) payoffs are linear in context, which is a feature vector. (Woodroofe 1979, Wang et al. 2005) and (Rigollet and Zeevi 2010) study contextual MAB with stochastic payoffs, under the name bandits with covariates: the context is a random variable correlated with the payoffs; they consider the case of two arms, and make some additional assumptions. Lazaric and Munos 2009 consider an online labeling problem with stochastic inputs and adversarially chosen labels; inputs and hypotheses (mappings from inputs to labels) can be thought of as “contexts” and “arms” respectively. Bandits with experts advice (e.g. Auer 2002) is the special case of contextual MAB where the context consists of experts’ advice; the advice of a each expert is modeled as a distributions over arms. All these papers are not directly applicable to the present setting.

Experimental work on contextual MAB includes (Pandey et al. 2007) and (Li et al. 2010, Li et al. 2011).

Lu et al. 2010 consider the setting in this paper for a product similarity space and, essentially, recover the uniform algorithm and a lower bound that matches (3). The same guarantee (3) can also be obtained as follows. The “uniform partition” described above can be used to define “experts” for a bandit-with-expert-advice algorithm such as exp4 (Auer et al. 2002b): for each set of the partition there is an expert whose advise is simply an arbitrary arm in this set. Then the regret bound for exp4 yields (3). Instead of exp4 one could use an algorithm in McMahan and Streeter 2009 which improves over exp4 if the experts are not “too distinct”; however, it is not clear if it translates into concrete improvements over (3).

If the context $x_{t}$ is time-invariant, our setting reduces to the Lipschitz MAB problem as defined in (Kleinberg et al. 2008b), which in turn reduces to continuum-armed bandits (Agrawal 1995, Kleinberg 2004, Auer et al. 2007) if the metric space is a real line, and to MAB with stochastic payoffs (Auer et al. 2002a) if the similarity information is absent.

Preliminaries

We will use the notation from the Introduction. In particular, $x_{t}$ will denote the $t$-th context arrival, i.e. the context that arrives in round $t$, and $y_{t}$ will denote the arm chosen by the algorithm in that round. We will use $x_{(1..T)}$ to denote the sequence of the first $T$ context arrivals $(x_{1}\,,\ \ldots\ ,x_{T})$. The badness of a point $(x,y)\in\mathcal{P}$ is defined as $\Delta(x,y)\triangleq\mu^{*}(x)-\mu(x,y)$. The context-specific best arm is

where ties are broken in an arbitrary but fixed way. To ensure that the $\max$ in (4) is attained by some $y\in Y$, we will assume that the similarity space $(\mathcal{P},\mathcal{D})$ is compact.

Metric spaces. Covering dimension and related notions are crucial throughout this paper. Let $\mathcal{P}$ be a set of points in a metric space, and fix $r>0$. An $r$-covering of $\mathcal{P}$ is a collection of subsets of $\mathcal{P}$, each of diameter strictly less than $r$, that cover $\mathcal{P}$. The minimal number of subsets in an $r$-covering is called the $r$-covering number of $\mathcal{P}$ and denoted $N_{r}(\mathcal{P})$. The covering number can be defined via radius-$r$ balls rather than diameter-$r$ sets. This alternative definition lacks the appealing “robustness” property: $N_{r}(\mathcal{P}^{\prime})\leq N_{r}(\mathcal{P})$ for any $\mathcal{P}^{\prime}\subset\mathcal{P}$, but (other than that) is equivalent for this paper. The covering dimension of $\mathcal{P}$ (with multiplier $c$) is the smallest $d$ such that $N_{r}(\mathcal{P})\leq c\,r^{-d}$ for each $r>0$. In particular, if $S$ is a subset of Euclidean space then its covering dimension is at most the linear dimension of $S$, but can be (much) smaller.

Covering is closely related to packing. A subset $S\subset\mathcal{P}$ is an $r$-packing of $\mathcal{P}$ if the distance between any two points in $S$ is at least $r$. The maximal number of points in an $r$-packing is called the $r$-packing number and denoted $N^{\mathtt{pack}}_{r}(\mathcal{P})$. It is well-known that $r$-packing numbers are essentially the same as $r$-covering numbers, namely $N_{2r}(\mathcal{P})\leq N^{\mathtt{pack}}_{r}(\mathcal{P})\leq N_{r}(\mathcal{P})$.

The doubling constant $c_{\textsc{dbl}}(\mathcal{P})$ of $\mathcal{P}$ is the smallest $k$ such that any ball can be covered by $k$ balls of half the radius. The doubling constant (and doubling dimension $\log c_{\textsc{dbl}}$) was introduced in Heinonen 2001 and has been a standard notion in theoretical computer science literature since Gupta et al. 2003. It was used to characterize tractable problem instances for a variety of problems (Talwar 2004, Kleinberg et al. 2009, Cole and Gottlieb 2006, e.g. see). It is known that $c_{\textsc{dbl}}(\mathcal{P})\geq c\,2^{d}$ if $d$ is the covering dimension of $\mathcal{P}$ with multiplier $c$, and that $c_{\textsc{dbl}}(\mathcal{P})\leq 2^{d}$ if $\mathcal{P}$ is a bounded subset of $d$-dimensional Euclidean space. A useful observation is that if distance between any two points in $S$ is $>r$, then any ball of radius $r$ contains at most $c_{\textsc{dbl}}$ points of $S$.

Accessing the similarity space. We assume full and computationally unrestricted access to the similarity information. While the issues of efficient representation thereof are important in practice, we believe that a proper treatment of these issues would be specific to the particular application and the particular similarity metric used, and would obscure the present paper. One clean formal way to address this issue is to assume oracle access: an algorithm accesses the similarity space via a few specific types of queries, and invokes an “oracle” that answers such queries.

Time horizon. We assume that the time horizon is fixed and known in advance. This assumption is without loss of generality in our setting. This is due to the well-known doubling trick which converts a bandit algorithm with a fixed time horizon into one that runs indefinitely and achieves essentially the same regret bound. Suppose for any fixed time horizon $T$ there is an algorithm $\mathtt{ALG}_{T}$ whose regret is at most $R(T)$. The new algorithm proceeds in phases $i=1,2,3,\ldots$ of duration $2^{i}$ rounds each, so that in each phase $i$ a fresh instance of $\mathtt{ALG}_{2^{i}}$ is run. This algorithm has regret $O(\log T)R(T)$ for each round $T$, and $O(R(T))$ in the typical case when $R(T)\geq T^{\gamma}$ for some constant $\gamma>0$.

The contextual zooming algorithm

In this section we consider the contextual MAB problem with stochastic payoffs. We present an algorithm for this problem, called contextual zooming, which takes advantage of both the “benign” context arrivals and the “benign” expected payoffs. The algorithm adaptively maintains a partition of the similarity space, “zooming in” on both the “popular” regions on the context space and the high-payoff regions of the arms space.

Contextual zooming extends the (context-free) zooming technique in (Kleinberg et al. 2008b), which necessitates a somewhat more complicated algorithm. In particular, selection and activation rules are defined differently, there is a new notion of “domains” and the distinction between “pre-index” and “index”. The analysis is more delicate, both the high-probability argument in Claim 4.4 and the subsequent argument that bounds the number of samples from suboptimal arms. Also, the key step of setting up the regret bounds is very different, especially for the improved regret bounds in Section 4.4.

Let us define the notions that express the performance of contextual zooming. These notions rely on the packing number $N_{r}(\cdot)$ in the similarity space $(\mathcal{P},\mathcal{D})$, and the more refined versions thereof that take into account “benign” expected payoffs and “benign” context arrivals.

Our guarantees have the following form, for some integer numbers $\{N_{r}\}_{r\in(0,1)}$:

Here and thereafter, $C_{0}=O(1)$ unless specified otherwise. In the pessimistic version, $N_{r}=N_{r}(\mathcal{P})$ is the $r$-packing number of $\mathcal{P}$. Then (5) can be simplified to $R(T)\leq\textstyle{\inf_{r\in(0,1)}}\,O\left(rT+\tfrac{1}{r}\,N_{r}(\mathcal{P})\log T\right)$ since $N_{r}(\mathcal{P})$ is non-increasing in $r$. The main contribution is refined bounds in which $N_{r}$ is smaller.

For every guarantee of the form (5), call it $N_{r}$-type guarantee, prior work (e.g., Kleinberg 2004, Kleinberg et al. 2008b, Bubeck et al. 2011a) suggests a more tractable dimension-type guarantee. This guarantee is in terms of the covering-type dimension induced by $N_{r}$, defined as follows: One standard definition of the covering dimension is (6) for $N_{r}=N_{r}(\mathcal{P})$ and $c=1$. Following Kleinberg et al. 2008b, we include an explicit dependence on $c$ in (6) to obtain a more efficient regret bound (which holds for any $c$).

Using (5) with $r_{0}=T^{-1/(d_{c}+2)}$, we obtain

For the pessimistic version ($N_{r}=N_{r}(\mathcal{P})$), the corresponding covering-type dimension $d_{c}$ is the covering dimension of the similarity space. The resulting guarantee (7) subsumes the bound (3) from prior work (because the covering dimension of a product similarity space is $d_{\text{X}}+d_{\text{Y}}$), and extends this bound from product similarity spaces (2) to arbitrary similarity spaces.

To account for “benign” expected payoffs, instead of $r$-packing number of the entire set $\mathcal{P}$ we consider the $r$-packing number of a subset of $\mathcal{P}$ which only includes points with near-optimal expected payoffs:

We define the $r$-zooming number as $N_{r}(\mathcal{P}_{\mu,r})$, the $r$-packing number of $\mathcal{P}_{\mu,r}$. The corresponding covering-type dimension (6) is called the contextual zooming dimension.

The $r$-zooming number can be seen as an optimistic version of $N_{r}(\mathcal{P})$: while equal to $N_{r}(\mathcal{P})$ in the worst case, it can be much smaller if the set of near-optimal context-arm pairs is “small” in terms of the packing number. Likewise, the contextual zooming dimension is an optimistic version of the covering dimension.

Consider the contextual MAB problem with stochastic payoffs. There is an algorithm (namely, Algorithm 4.2 described below) whose contextual regret $R(T)$ satisfies (5) with $N_{r}$ equal to $N_{r}(\mathcal{P}_{\mu,r})$, the $r$-zooming number. Consequently, $R(T)$ satisfies the dimension-type guarantee (7), where $d_{c}$ is the contextual zooming dimension.

In Theorem 4.1, the same algorithm enjoys the bound (7) for each $c>0$. This is a useful trade-off since different values of $c$ may result in drastically different values of the dimension $d_{c}$. On the contrary, the “uniform algorithm” from prior work essentially needs to take the $c$ as input.

Further refinements to take into account “benign” context arrivals are deferred to Section 4.4.

2 Description of the algorithm

The algorithm is parameterized by the time horizon $T$. In each round $t$, it maintains a finite collection $\mathcal{A}_{t}$ of balls in $(\mathcal{P},\mathcal{D})$ (called active balls) which collectively cover the similarity space. Adding active balls is called activating; balls stay active once they are activated. Initially there is only one active ball which has radius $1$ and therefore contains the entire similarity space.

At a high level, each round $t$ proceeds as follows. Context $x_{t}$ arrives. Then the algorithm selects an active ball $B$ and an arm $y_{t}$ such that $(x_{t},y_{t})\in B$, according to the “selection rule”. Arm $y_{t}$ is played. Then one ball may be activated, according to the “activation rule”.

In order to state the two rules, we need to put forward several definitions. Fix an active ball $B$ and round $t$. Let $r(B)$ be the radius of $B$. The confidence radius of $B$ at time $t$ is

where $n_{t}(B)$ is the number of times $B$ has been selected by the algorithm before round $t$. The domain of ball $B$ in round $t$ is a subset of $B$ that excludes all balls $B^{\prime}\in\mathcal{A}_{t}$ of strictly smaller radius:

We will also denote (10) as $\mathtt{dom\,}(B,\mathcal{A}_{t})$. Ball $B$ is called relevant in round $t$ if $(x_{t},y)\in\mathtt{dom\,}_{t}(B)$ for some arm $y$. In each round, the algorithm selects one relevant ball $B$. This ball is selected according to a numerical score $I_{t}(B)$ called index. (The definition of index is deferred to the end of this subsection.)

Now we are ready to state the two rules, for every given round $t$.

selection rule. Select a relevant ball $B$ with the maximal index (break ties arbitrarily). Select an arbitrary arm $y$ such that $(x_{t},y)\in\mathtt{dom\,}_{t}(B)$.

activation rule. Suppose the selection rule selects a relevant ball $B$ such that $\mathtt{conf}_{t}(B)\leq r(B)$ after this round. Then, letting $y$ be the arm selected in this round, a ball with center $(x_{t},y)$ and radius $\tfrac{1}{2}\,r(B)$ is activated. ($B$ is then called the parent of this ball.)

It remains to define the index $I_{t}(B)$. Let $\mathtt{rew}_{t}(B)$ be the total payoff from all rounds up to $t-1$ in which ball $B$ has been selected by the algorithm. Then the average payoff from $B$ is $\nu_{t}(B)\triangleq\tfrac{\mathtt{rew}_{t}(B)}{\max(1,\;n_{t}(B))}$. The pre-index of $B$ is defined as the average $\nu_{t}(B)$ plus an “uncertainty term”:

The “uncertainty term” in (11) reflects both uncertainty due to a location in the metric space, via $r(B)$, and uncertainty due to an insufficient number of samples, via $\mathtt{conf}_{t}(B)$.

The index of $B$ is obtained by taking a minimum over all active balls $B^{\prime}$:

where $\mathcal{D}(B,B^{\prime})$ is the distance between the centers of the two balls.

The meaning of index and pre-index is as follows. Both are upper confidence bound (UCB, for short) for expected rewards in $B$. Pre-index is a UCB for $\mu(B)$, the expected payoff from the center of $B$; essentially, it is the best UCB on $\mu(B)$ that can be obtained from the observations of $B$ alone. The $\min$ expression in (12) is an improved UCB on $\mu(B)$, refined using observations from all other active balls. Finally, index is, essentially, the best available UCB for the expected reward of any pair $(x,y)\in B$.

Relevant balls are defined through the notion of the “domain” to ensure the following property: in each round when a parent ball is selected, some other ball is activated. This property allows us to “charge” the regret accumulated in each such round to the corresponding activated ball.

Running time.

The running time is dominated by determining which active balls are relevant. Formally, we assume an oracle that inputs context $x$ and a finite sequence $(B,B_{1}\,,\ \ldots\ ,B_{n})$ of balls in the similarity space, and outputs an arm $y$ such that $(x,y)\in B\setminus\cup_{j=1}^{n}B_{j}$ if such arm exists, and null otherwise. Then each round $t$ can be implemented via $n_{t}$ oracle calls with $n<n_{t}$ balls each, where $n_{t}$ is the current number of active balls. Letting $f(n)$ denote the running time of one oracle call in terms of $n$, the running time for each round the algorithm is at most $n_{T}\,f(n_{T})$.

3 Analysis of the algorithm: proof of Theorem 4.1

We start by observing that the activation rule ensures several important invariants.

(confidence) for all times $t$ and all active balls $B$,

(covering) in each round $t$, the domains of active balls cover the similarity space.

(separation) for any two active balls of radius $r$, their centers are at distance at least $r$.

The confidence invariant is immediate from the activation rule.

For the covering invariant, note that $\cup_{B\in\mathcal{A}}\,\mathtt{dom\,}(B,\mathcal{A})=\cup_{B\in\mathcal{A}}\,B$ for any finite collection $\mathcal{A}$ of balls in the similarity space. (For each $v\in\cup_{B\in\mathcal{A}}\,B$, consider a smallest radius ball in $\mathcal{A}$ that contains $B$. Then $v\in\mathtt{dom\,}(B,\mathcal{A})$.) The covering invariant then follows since $\mathcal{A}_{t}$ contains a ball that covers the entire similarity space.

To show the separation invariant, let $B$ and $B^{\prime}$ be two balls of radius $r$ such that $B$ is activated at time $t$, with parent $B^{\text{par}}$, and $B^{\prime}$ is activated before time $t$. The center of $B$ is some point $(x_{t},y_{t})\in\mathtt{dom\,}(B^{\text{par}},\mathcal{A}_{t})$. Since $r(B^{\text{par}})>r(B^{\prime})$, it follows that $(x_{t},y_{t})\not\in B^{\prime}$. ∎

Throughout the analysis we will use the following notation. For a ball $B$ with center $(x,y)\in\mathcal{P}$, define the expected payoff of $B$ as $\mu(B)\triangleq\mu(x,y)$. Let $B_{t}^{\mathtt{sel}}$ be the active ball selected by the algorithm in round $t$. Recall that the badness of $(x,y)\in\mathcal{P}$ is defined as $\Delta(x,y)\triangleq\mu^{*}(x)-\mu(x,y)$.

If ball $B$ is active in round $t$, then with probability at least $1-T^{-2}$ we have that

Fix ball $V$ with center $(x,y)$. Let $S$ be the set of rounds $s\leq t$ when ball $B$ was selected by the algorithm, and let $n=|S|$ be the number of such rounds. Then $\nu_{t}(B)=\tfrac{1}{n}\,\textstyle{\sum_{s\in S}}\;\pi_{s}(x_{s},y_{s})$.

Note that (13) implies $I^{\text{pre}}(B)\geq\mu(B)$, so that $I^{\text{pre}}(B)$ is indeed a UCB on $\mu(B)$.

Call a run of the algorithm clean if (13) holds for each round. From now on we will focus on a clean run, and argue deterministically using (13). The heart of the analysis is the following lemma.

Consider a clean run of the algorithm. Then $\Delta(x_{t},y_{t})\leq 14\,r(B_{t}^{\mathtt{sel}})$ in each round $t$.

Fix round $t$. By the covering invariant, $(x_{t},\,y^{*}(x_{t}))\in B$ for some active ball $B$. Recall from (12) that $I_{t}(B)=r(B)+I^{\text{pre}}(B^{\prime})+\mathcal{D}(B,B^{\prime})$ for some active ball $B^{\prime}$. Therefore

On the other hand, letting $B^{\text{par}}$ be the parent of $B_{t}^{\mathtt{sel}}$ and noting that by the activation rule

we can upper-bound $I_{t}(B_{t}^{\mathtt{sel}})$ as follows:

Putting the pieces together, $\mu^{*}(x_{t})\leq I_{t}(B_{t}^{\mathtt{sel}})\leq\mu(x_{t},y_{t})+14\,r(B_{t}^{\mathtt{sel}})$. ∎

In a clean run, if ball $B$ is activated in round $t$ then $\Delta(x_{t},y_{t})\leq 10\,r(B)$.

By the activation rule, $B_{t}^{\mathtt{sel}}$ is the parent of $B$. Thus by Lemma 4.5 we immediately have $\Delta(x_{t},y_{t})\leq 14\,r(B_{t}^{\mathtt{sel}})=28\,r(B)$.

To obtain the constant of 10 that is claimed here, we prove a more efficient special case of Lemma 4.5:

To prove (18), we simply replace (17) in the proof of Lemma 4.5 by similar inequality in terms of $I^{\text{pre}}(B_{t}^{\mathtt{sel}})$ rather than $I^{\text{pre}}(B^{\text{par}})$:

For the last inequality, we use the fact that $\mathtt{conf}_{t}(B_{t}^{\mathtt{sel}})\leq r(B_{t}^{\mathtt{sel}})$ whenever $B_{t}^{\mathtt{sel}}$ is a parent ball. ∎

If ball $B\in\mathcal{F}_{r}$ is activated in round $t$, then Corollary 4.6 asserts that its center $(x_{t},y_{t})$ lies in the set $\mathcal{P}_{\mu,r}$, as defined in (8). By the separation invariant, the centers of balls in $\mathcal{F}_{r}$ are within distance at least $r$ from one another. It follows that $|\mathcal{F}_{r}|\leq N_{r}$, where $N_{r}$ is the $r$-zooming number.

Fixing some $r_{0}\in(0,1)$, note that in each rounds $t$ when a ball of radius $<r_{0}$ was selected, regret is $\Delta(x_{t},y_{t})\leq O(r_{0})$, so the total regret from all such rounds is at most $O(r_{0}\,T)$. Therefore, contextual regret can be written as follows:

The $N_{r}$-type regret guarantee in Theorem 4.1 follows by taking $\inf$ on all $r_{0}\in(0,1)$.

4 Improved regret bounds

Let us provide regret bounds that take into account “benign” context arrivals. The main difficulty here is to develop the corresponding definitions; the analysis then carries over without much modification. The added value is two-fold: first, we establish the intuition that benign context arrivals matter, and then the specific regret bound is used in Section 6.2 to match the result in Slivkins and Upfal 2008.

A crucial step in the proof of Theorem 4.1 is to bound the number of active radius-$r$ balls by $N_{r}(\mathcal{P}_{\mu,r})$, which is accomplished by observing that their centers form an $r$-packing $S$ of $\mathcal{P}_{\mu,r}$. We make this step more efficient, as follows. An active radius-$r$ ball is called full if $\mathtt{conf}_{t}(B)\leq r$ for some round $t$. Note that each active ball is either full or a child of some other ball that is full. The number of children of a given ball is bounded by the doubling constant of the similarity space. Thus, it suffices to consider the number of active radius-$r$ balls that are full, which is at most $N_{r}(\mathcal{P}_{\mu,r})$, and potentially much smaller.

Consider active radius-$r$ active balls that are full. Their centers form an $r$-packing $S$ of $\mathcal{P}_{\mu,r}$ with an additional property: each point $p\in S$ is assigned at least $1/r^{2}$ context arrivals $x_{t}$ so that $(x_{t},y)\in B(p,r)$ for some arm $y$, and each context arrival is assigned to at most one point in $S$. Namely, each point $p\in S$ is assigned all contexts $x_{t}$ such that the corresponding ball is chosen in round $t$. A set $S\subset\mathcal{P}$ with this property is called $r$-consistent (with context arrivals). The adjusted $r$-packing number of a set $\mathcal{P}^{\prime}\subset\mathcal{P}$, denoted $N^{\text{adj}}_{r}(\mathcal{P}^{\prime})$, is the maximal size of an $r$-consistent $r$-packing of $\mathcal{P}^{\prime}$. It can be much smaller than the $r$-packing number of $\mathcal{P}^{\prime}$ if most context arrivals fall into a small region of the similarity space.

We make one further optimization, tailored to the application in Section 6.2. Informally, we take advantage of context arrivals $x_{t}$ such that expected payoff $\mu(x_{t},y)$ is either optimal or very suboptimal. A point $(x,y)\in\mathcal{P}$ is called an $r$-winner if for each $(x^{\prime},y^{\prime})\in B((x,y),\,2r)$ it holds that $\mu(x^{\prime},y^{\prime})=\mu^{*}(x^{\prime})$. Let $\mathcal{W}_{\mu,r}$ be the set of all $r$-winners. It is easy to see that if $B$ is a radius-$r$ ball centered at an $r$-winner, and $B$ or its child is selected in a given round, then this round does not contribute to contextual regret. Therefore, it suffices to consider ($r$-consistent) $r$-packings of $\mathcal{P}_{\mu,r}\setminus\mathcal{W}_{\mu,r}$.

Our final guarantee is in terms of $N^{\text{adj}}(\mathcal{P}_{\mu,r}\setminus\mathcal{W}_{\mu,r})$, which we term the adjusted $r$-zooming number.

Consider the contextual MAB problem with stochastic payoffs. The contextual regret $R(T)$ of the contextual zooming algorithm satisfies (5), where $N_{r}$ is the adjusted $r$-zooming number and $C_{0}$ is the doubling constant of the similarity space times some absolute constant. Consequently, $R(T)$ satisfies the dimension-type guarantee (7), where $d_{c}$ is the corresponding covering-type dimension.

Lower bounds

We match the upper bound in Theorem 4.1 up to $O(\log T)$ factors. Our lower bound is very general: it applies to an arbitrary product similarity space, and moreover for a given similarity space it matches, up to $O(\log T)$ factors, any fixed value of the upper bound (as explained below).

We construct a distribution $\mathcal{I}$ over problem instances on a given metric space, so that the lower bound is for a problem instance drawn from this distribution. A single problem instance would not suffice to establish a lower bound because a trivial algorithm that picks arm $y^{*}(x)$ for each context $x$ will achieve regret $0$.

The distribution $\mathcal{I}$ satisfies the following two properties: the upper bound in Theorem 4.1 is uniformly bounded from above by some number $R$, and any algorithm must incur regret at least $\Omega(R/\log T)$ in expectation over $\mathcal{I}$. Moreover, we constrict such $\mathcal{I}$ for every possible value of the upper bound in Theorem 4.1 on a given metric space, i.e. not just for problem instances that are “hard” for this metric space.

To formulate our result, let $R^{\text{UB}}_{\mu}(T)$ denote the upper bound in Theorem 4.1, i.e. is the right-hand side of (5) where $N_{r}=N_{r}(\mathcal{P}_{\mu,r})$ is the $r$-zooming number. Let $R^{\text{UB}}(T)$ denote the pessimistic version of this bound, namely right-hand side of (5) where $N_{r}=N_{r}(\mathcal{P})$ is the packing number of $\mathcal{P}$.

Consider the contextual MAB problem with stochastic payoffs, Let $(\mathcal{P},\mathcal{D})$ be a product similarity space. Fix an arbitrary time horizon $T$ and a positive number $R\leq R^{\text{UB}}(T)$. Then there exists a distribution $\mathcal{I}$ over problem instances on $(\mathcal{P},\mathcal{D})$ with the following two properties:

$R^{\text{UB}}_{\mu}(T)\leq O(R)$ for each problem instance in $\mathtt{support}(\mathcal{I})$.

To prove this theorem, we build on the lower-bounding technique from Auer et al. 2002b, and its extension to (context-free) bandits in metric spaces in Kleinberg 2004. In particular, we use the basic needle-in-the-haystack example from Auer et al. 2002b, where the “haystack” consists of several arms with expected payoff $\tfrac{1}{2}$, and the “needle” is an arm whose expected payoff is slightly higher.

Our construction is parameterized by two numbers: $r\in(0,\tfrac{1}{2}]$ and $N\leq N_{r}(\mathcal{P})$, where $N_{r}(\mathcal{P})$ is the $r$-packing number of $\mathcal{P}$. Given these parameters, we construct a collection $\mathcal{I}=\mathcal{I}_{N,r}$ of $\Theta(N)$ problem instances as follows.

Let $N_{{\text{X}},r}$ be the $r$-packing number of $X$ in the context space, and let $N_{{\text{Y}},r}$ be the $r$-packing number of $Y$ in the arms space. Note that $N_{r}(\mathcal{P})=N_{{\text{X}},r}\times N_{{\text{Y}},r}$. For simplicity, let us assume that $N=n_{\text{X}}\,n_{\text{Y}}$, where $1\leq n_{X}\leq N_{{\text{X}},r}$ and $2\leq n_{\text{Y}}\leq N_{{\text{Y}},r}$.

An $r$-net is the set $S$ of points in a metric space such that any two points in $S$ are at distance $>r$ from each other, and each point in the metric space is within distance $\leq r$ from some point in $S$. Recall that any $r$-net on the context space has size at least $N_{{\text{X}},r}$. Let $S_{\text{X}}$ be an arbitrary set of $n_{\text{X}}$ points from one such $r$-net. Similarly, let $S_{\text{Y}}$ be an arbitrary set of $n_{\text{Y}}$ points from some $r$-net on the arms space. The sequence $x_{(1..T)}$ of context arrivals is any fixed permutation over the points in $S_{\text{X}}$, repeated indefinitely.

All problem instances in $\mathcal{I}$ have 0-1 payoffs. For each $x\in S_{\text{X}}$ we construct a needle-in-the-haystack example on the set $S_{\text{Y}}$. Namely, we pick one point $y^{*}(x)\in S_{\text{Y}}$ to be the “needle”, and define $\mu(x,y^{*}(x))=\tfrac{1}{2}+\tfrac{r}{4}$, and $\mu(x,y)=\tfrac{1}{2}+\tfrac{r}{8}$ for each $y\in S_{\text{Y}}\setminus\{y^{*}(x)\}$. We smoothen the expected payoffs so that far from $S_{\text{X}}\times S_{\text{Y}}$ expected payoffs are $\tfrac{1}{2}$ and the Lipschitz condition (1) holds:

Note that we obtain a distinct problem instance for each function $y^{*}(\cdot):S_{\text{X}}\to S_{\text{Y}}$. This completes our construction.

Analysis.

The useful properties of the above construction are summarized in the following lemma:

Fix $r\in(0,\tfrac{1}{2}]$ and $N\leq N_{r}(\mathcal{P})$. Let $\mathcal{I}=\mathcal{I}_{N,r}$ and $T_{0}=N\,r^{-2}$. Then:

for each problem instance in $\mathcal{I}$ it holds that $R^{\text{UB}}_{\mu}(T_{0})\leq O(N/r)(\log T_{0})$.

For the lower bound in Lemma 5.2, the idea is that in $T$ rounds each context in $S_{\text{X}}$ contributes $\Omega(|S_{\text{Y}}|/r)$ to contextual regret, resulting in total contextual regret $\Omega(N/r)$.

Before we proceed to prove Lemma 5.2, let us use it to derive Theorem 5.1. Fix an arbitrary time horizon $T$ and a positive number $R\leq R^{\text{UB}}(T)$. Recall that since $N_{r}(\mathcal{P})$ is non-increasing in $r$, for some constant $C>0$ it holds that

Let $r=\frac{R}{2C\,T(1+\log T)}$. Then $r\leq\tfrac{1}{2}$ and $Tr^{2}\leq N_{r}(\mathcal{P})$.

Denote $k(r)=N_{r}(\mathcal{P})$ and consider function $f(r)\triangleq k(r)/r^{2}$. This function is non-increasing in $r$; $f(1)=1$ and $f(r)\to\infty$ for $r\to 0$. Therefore there exists $r_{0}\in(0,1)$ such that $f(r_{0})\leq T\leq f(r_{0}/2)$. Re-writing this, we obtain

Thus $r\leq r_{0}/2$ and finally $T\,r^{2}\leq T\,r_{0}^{2}/4\leq k(r_{0}/2)\leq k(r)=N_{r}(\mathcal{P})$. ∎

So, Lemma 5.2 with $r\triangleq\frac{R}{2C\,T(1+\log T)}$ and $N\triangleq T\,r^{2}$. implies Theorem 5.1.

1 Proof of Lemma 5.2

Collection $\mathcal{I}$ consists of valid instances of contextual MAB problem with similarity space $(\mathcal{P},\mathcal{D})$.

We need to prove that each problem instance in $\mathcal{P}$ satisfies the Lipschitz condition (1). Assume the Lipschitz condition (1) is violated for some points $(x,y),\,(x^{\prime},y^{\prime})\in X\times Y$. For brevity, let $p=(x,y)$, $p^{\prime}=(x^{\prime},y^{\prime})$, and let us write $\mu(p)\triangleq\mu(x,y)$. Then $|\mu(p)-\mu(p^{\prime})|>\mathcal{D}(p,p^{\prime})$.

By (19), $\mu(\cdot)\in[\tfrac{1}{2},\tfrac{1}{2}+\tfrac{r}{4}]$, so $\mathcal{D}(p,p^{\prime})<\tfrac{r}{4}$.

Without loss of generality, $\mu(p)>\mu(p^{\prime})$. In particular, $\mu(p)>\tfrac{1}{2}$. Therefore there exists $p_{0}=(x_{0},y_{0})\in S_{\text{X}}\times S_{\text{Y}}$ such that $\mathcal{D}(p,p_{0})<\tfrac{r}{4}$. Then $\mathcal{D}(p^{\prime},p_{0})<\tfrac{r}{2}$ by triangle inequality.

Now, for any other $p^{\prime}_{0}\in S_{\text{X}}\times S_{\text{Y}}$ it holds that $\mathcal{D}(p_{0},p^{\prime}_{0})>r$, and thus by triangle inequality $\mathcal{D}(p,p^{\prime}_{0})>\tfrac{3r}{4}$ and $\mathcal{D}(p^{\prime},p^{\prime}_{0})>\tfrac{r}{2}$. It follows that (19) can be simplified as follows:

For each instance in $\mathcal{P}$ and $T_{0}=N\,r^{-2}$ it holds that $R^{\text{UB}}_{\mu}(T_{0})\leq O(N/r)(\log T_{0})$.

Recall that $R^{\text{UB}}_{\mu}(T_{0})$ is the right-hand side of (5) with $N_{r}=N_{r}(\mathcal{P}_{\mu,r})$, where $\mathcal{P}_{\mu,r}$ is defined by (8).

Fix $r^{\prime}>0$. It is easy to see that

It follows that $N_{r^{\prime}}(\mathcal{P}_{\mu,r^{\prime}})\leq N$ whenever $r^{\prime}\geq\tfrac{r}{4}$. Therefore, taking $r_{0}=\tfrac{r}{4}$ in (5), we obtain

Let $R(x,T)$ be the contribution of each context $x\in S_{\text{X}}$ to contextual regret:

where $y_{t}$ is the arm chosen by the algorithm in round $t$. Our goal is to show that $R(x,T_{0})\geq\Omega(r\,n_{\text{Y}})$.

We will consider each context $x\in S_{\text{X}}$ separately: the rounds when $x$ arrives form an instance $I_{x}$ of a context-free bandit problem that lasts for $T_{0}/n_{\text{X}}=n_{\text{Y}}\,r^{-2}$ rounds, where expected payoffs are given by $\mu(x,\cdot)$ as defined in (19). Let $\mathcal{I}_{x}$ be the family of all such instances $I_{x}$.

A uniform distribution over $\mathcal{I}$ can be reformulated as follows: for each $x\in S_{\text{X}}$, pick the “needle” $y^{*}(x)$ independently and uniformly at random from $S_{\text{Y}}$. This induces a uniform distribution over instances in $\mathcal{I}_{x}$, for each context $x\in S_{\text{X}}$. Informally, knowing full or partial information about $y^{*}(x)$ for some $x$ reveals no information whatsoever about $y^{*}(x^{\prime})$ for any $x^{\prime}\neq x$.

Thus, it remains to handle each $\mathcal{I}_{x}$ separately: i.e., to prove that the expected regret of any bandit algorithm on an instance drawn uniformly at random from $\mathcal{I}_{x}$ is at least $\Omega(r\,n_{\text{Y}})$. We use the KL-divergence technique that originated in Auer et al. 2002b. If the set of arms were exactly $S_{\text{Y}}$, then the desired lower bound would follow from Auer et al. 2002b directly. To handle the problem instances in $\mathcal{I}_{x}$, we use an extension of the technique from Auer et al. 2002b, which is implicit in Kleinberg 2004 and encapsulated as a stand-alone theorem in Kleinberg et al. 2013. We restate this theorem as Theorem A.2 in Appendix A.

It is easy to check that the family $\mathcal{I}_{x}$ of problem instances satisfies the preconditions in Theorem A.2. Fix $x\in S_{\text{X}}$. For a given choice of the “needle” $y^{*}=y^{*}(x)\in S_{\text{Y}}$, let $\mu(x,y\,|\,y^{*})$. be the expected payoff of each arm $y$, and let $\nu_{y^{*}}(\cdot)=\mu(x,\cdot\,|\,y^{*})$ be the corresponding payoff function for the bandit instance $I_{x}$. Then $\{\nu_{y^{*}}\}$, $y^{*}\in S_{\text{Y}}$ is an “$(\epsilon,k)$-ensemble” for $\epsilon=\tfrac{r}{8}$ and $k=|S_{\text{Y}}|$. ∎

Applications of contextual zooming

We describe several applications of contextual zooming: to MAB with slow adversarial change (Section 6.1), to MAB with stochastically evolving payoffs (Section 6.2), and to the “sleeping bandits” problem (Section 6.3). In particular, we recover some of the main results in Slivkins and Upfal 2008 and Kleinberg et al. 2008a. Also, in Section 6.4 we discuss a recent application of contextual zooming to bandit learning-to-rank, which has been published in Slivkins et al. 2013.

Consider the (context-free) adversarial MAB problem in which expected payoffs of each arm change over time gradually. Specifically, we assume that expected payoff of each arm $y$ changes by at most $\sigma_{y}$ in each round, for some a-priori known volatilities $\sigma_{y}$. The algorithm’s goal here is continuously adapt to the changing environment, rather than converge to the best fixed mapping from contexts to arms. We call this setting the drifting MAB problem.

Formally, our benchmark is a fictitious algorithm which in each round selects an arm that maximizes expected payoff for the current context. The difference in expected payoff between this benchmark and a given algorithm is called dynamic regret of this algorithm. It is easy to see that the worst-case dynamic regret of any algorithm cannot be sublinear in time. For example, consider problem instances with two arms such that the payoff of each arm in each round is either $\tfrac{1}{2}$ or $\tfrac{1}{2}+\sigma$ (and can change from round to round). Over this family of problem instances, dynamic regret in $T$ rounds is at least $\tfrac{1}{2}\,\sigma T$. We are primarily interested in algorithm’s long-term performance, as quantified by average dynamic regret $\hat{R}(T)\triangleq R(T)/T$. Our goal is to bound the limit $\lim_{T\to\infty}\hat{R}(T)$ in terms of the parameters: the number of arms and the volatilities $\sigma_{y}$. (In general, such upper bound is non-trivial as long as it is smaller than 1, since all payoffs are at most 1.)

We restate this setting as a contextual MAB problem with stochastic payoffs in which the $t$-th context arrival is simply $x_{t}=t$. Then $\mu(t,y)$ is the expected payoff of arm $y$ at time $t$, and dynamic regret coincides with contextual regret specialized to the case $x_{t}=t$. Each arm $y$ satisfies a “temporal constraint”:

for some constant $\sigma_{y}$. To set up the corresponding similarity space $(\mathcal{P},\mathcal{D})$, let $\mathcal{P}=[T]\times Y$, and

Our solution for the drifting MAB problem is the contextual zooming algorithm parameterized by the similarity space $(\mathcal{P},\mathcal{D})$. To obtain guarantees for the long-term performance, we run contextual zooming with a suitably chosen time horizon $T_{0}$, and restart it every $T_{0}$ rounds; we call this version contextual zooming with period $T_{0}$. Periodically restarting the algorithm is a simple way to prevent the change over time from becoming too large; it suffices to obtain strong provable guarantees.

The general provable guarantees are provided by Theorem 4.1 and Theorem 4.7. Below we work out some specific, tractable corollaries.

Consider the drifting MAB problem with $k$ arms and volatilities $\sigma_{y}\equiv\sigma$. Contextual zooming with period $T_{0}$ has average dynamic regret $\hat{R}(T)=O(k\sigma\log T_{0})^{1/3}$, whenever $T\geq T_{0}\geq(\tfrac{k}{\sigma^{2}})^{1/3}\,\log\tfrac{k}{\sigma}$.

It suffices to upper-bound regret in a single period. Indeed, if $R(T_{0})\leq R$ for any problem instance, then $R(T)\leq R\,{\lceil{T/T_{0}}\rceil}$ for any $T>T_{0}$. It follows that $\hat{R}(T)\leq 2\,\hat{R}(T_{0})$. Therefore, from here on we can focus on analyzing contextual zooming itself, rather than contextual zooming with a period.

The main step is to derive the regret bound (5) with a specific upper bound on $N_{r}$. We will show that

Plugging $N_{r}\leq k\,(1+\tfrac{T\sigma}{r})$ into (5) and taking $r_{0}=(k\sigma\log T)^{1/3}$ we obtain This choice of $r_{0}$ minimizes the $\inf$ expression in (5) up to constant factors by equating the two summands.

Therefore, for any $T\geq(\tfrac{k}{\sigma^{2}})^{1/3}\,\log\tfrac{k}{\sigma}$ we have $\hat{R}(T)=O(k\sigma\log T)^{1/3}$.

It remains to prove (23). We use a pessimistic version of Theorem 4.1: (5) with $N_{r}=N_{r}(\mathcal{P})$, the $r$-packing number of $\mathcal{P}$. Fix $r\in(0,1]$. For any $r$-packing $S$ of $\mathcal{P}$ and each arm $y$, each time interval $I$ of duration $\Delta_{r}\triangleq r/\sigma$ provides at most one point for $S$: there exists at most one time $t\in I$ such that $(t,y)\in S$. Since there are at most ${\lceil{T/\Delta_{r}}\rceil}$ such intervals $I$, it follows that $N_{r}(\mathcal{P})\leq k\,{\lceil{T/\Delta_{r}}\rceil}\leq k\,(1+T\tfrac{\sigma}{r})$. ∎

The restriction $\sigma_{y}\equiv\sigma$ is non-essential: it is not hard to obtain the same bound with $\sigma=\tfrac{1}{k}\sum_{y}\sigma_{y}$. Modifying the construction in Section 5 (details omitted from this version) one can show that Corollary 6.1 is optimal up to $O(\log T)$ factors.

The temporal version ($x_{t}=t$) of our contextual MAB setting with stochastic payoffs subsumes the drifting MAB problem and furthermore allows to combine the temporal constraints (21) described above (for each arm, across time) with ‘‘spatial constraints” (for each time, across arms). To the best of our knowledge, such MAB models are quite rare in the literature. The only other MAB model with this flavor that we are aware of, found in Hazan and Kale 2009, combines linear payoffs and bounded “total variation” (aggregate temporal change) of the cost functions. A clean example is

where $(Y,\mathcal{D}_{\text{Y}})$ is the arms space. For this example, we can obtain an analog of Corollary 6.1, where the regret bound depends on the covering dimension of the arms space $(Y,\mathcal{D}_{\text{Y}})$.

Consider the drifting MAB problem with spatial constraints (24), where $\sigma$ is the volatility. Let $d$ be the covering dimension of the arms space, with multiplier $k$. Contextual zooming with period $T_{0}$ has average dynamic regret $\hat{R}(T)=O(k\,\sigma\log T_{0})^{\tfrac{1}{d+3}}$, whenever $T\geq T_{0}\geq k^{\tfrac{1}{d+3}}\;\sigma^{-\tfrac{d+2}{d+3}}\;\log\tfrac{k}{\sigma}$.

We obtain Corollary 6.1 as a special case by setting $d=0$.

It suffices to bound $\hat{R}(T_{0})$ for (non-periodic) contextual zooming. First we bound the $r$-covering number of the similarity space $(\mathcal{P},\mathcal{D})$:

where $N_{r}^{\text{X}}(\cdot)$ is the $r$-covering number in the context space, and $N_{r}^{\text{Y}}(\cdot)$ is that in the arms space. We worked out the former for Corollary 6.1. Plugging this into (5) and taking $r_{0}=(k\,\sigma\log T)^{1/(3+d)}$, we obtain

The desired bound on $\hat{R}(T_{0})$ follows easily. ∎

2 Bandits with stochastically evolving payoffs

We consider a special case of drifting MAB problem in which expected payoffs of each arm evolve over time according to a stochastic process with a uniform stationary distribution. We obtain improved regret bounds for contextual zooming, taking advantage of the full power of our analysis in Section 4.

In particular, we address a version in which the stochastic process is a random walk with step $\pm\sigma$. This version has been previously studied in Slivkins and Upfal 2008 under the name “Dynamic MAB”. For the main case ($\sigma_{i}\equiv\sigma$), our regret bound for Dynamic MAB matches that in Slivkins and Upfal 2008.

To improve the flow of the paper, the proofs are deferred to Appendix 7.

We obtain a stronger version of (23) via Theorem 4.7. To use this theorem, we need to bound the adjusted $r$-zooming number, call it $N_{r}$. We show that

Then we obtain a different bound on dynamic regret, which is stronger than Corollary 6.1 for $k<\sigma^{-1/2}$.

The crux of the proof is to show (25). Interestingly, it involves using all three optimizations in Theorem 4.7: $N_{r}(\mathcal{P}_{\mu,r})$, $N_{r}(\mathcal{P}_{\mu,r}\setminus\mathcal{W}_{\mu,r})$ and $N^{\text{adj}}_{r}(\cdot)$, whereas any two of them do not seem to suffice. The rest is a straightforward computation similar to the one in Corollary 6.1.

Dynamic MAB.

According to a well-known fact about random walks, For example, this follows as a simple application of Azuma-Hoeffding inequality.

We use contextual zooming with period $T_{0}$, but we parameterize it by a different similarity space $(\mathcal{P},\mathcal{D}_{T_{0}})$ that we define according to (26). Namely, we set

The following corollary is proved using the same technique as Corollary 6.3:

3 Sleeping bandits

The sleeping bandits problem Kleinberg et al. 2008a is an extension of MAB where in each round some arms can be “asleep”, i.e. not available in this round. One of the main results in Kleinberg et al. 2008a is on sleeping bandits with stochastic payoffs. We recover this result using contextual zooming.

We model sleeping bandits as contextual MAB problem where each context arrival $x_{t}$ corresponds to the set of arms that are “awake” in this round. More precisely, for every subset $S\subset Y$ of arms there is a distinct context $x_{S}$, and $\mathcal{P}=\{(x_{S},y):\,y\in S\subset Y\}$. is the set of feasible context-arm pairs. The similarity distance is simply $\mathcal{D}((x,y),\,(x^{\prime},y^{\prime}))=\mathbf{1}_{\{y\neq y^{\prime}\}}$. Note that the Lipschitz condition (1) is satisfied.

For this setting, contextual zooming essentially reduces to the “highest awake index” algorithm in Kleinberg et al. 2008a. In fact, we can re-derive the result Kleinberg et al. 2008a on sleeping MAB with stochastic payoffs as an easy corollary of Theorem 4.1.

Consider the sleeping MAB problem with stochastic payoffs. Order the arms so that their expected payoffs are $\mu_{1}\leq\mu_{2}\leq\ldots\leq\mu_{n}$, where $n$ is the number of arms. Let $\Delta_{i}=\mu_{i+1}-\mu_{i}$. Then

The $r$-zooming number $N_{r}(\mathcal{P}_{\mu,r})$ is equal to the number of distinct arms in $\mathcal{P}_{\mu,r}$, i.e. the number of arms $i\in Y$ such that $\Delta(x,i)\leq 12r$ for some context $x$. Note that for a given arm $i$, the quantity $\Delta(x,i)$ is minimized when the set of awake arms is $S=\{i,i+1\}$. Therefore, $N_{r}(\mathcal{P}_{\mu,r})$ is equal to the number of arms $i\in Y$ such that $\Delta_{i}\leq 12r$. It follows that

Moreover, the contextual MAB problem extends the sleeping bandits setting by incorporating similarity information on arms. The contextual zooming algorithm (and its analysis) applies, and is geared to exploit this additional similarity information.

4 Bandit learning-to-rank

Following a preliminary publication of this paper on arxiv.org, contextual zooming has been applied in Slivkins et al. 2013 to bandit learning-to-rank. Interestingly, the “contexts” studied in Slivkins et al. 2013 are very different from what we considered so far.

The basic setting, motivated by web search, was introduced in Radlinski et al. 2008. In each round a new user arrives. The algorithm selects a ranked list of $k$ documents and presents it to the user who clicks on at most one document, namely on the first document that (s)he finds relevant. A user is specified by a binary vector over documents. The goal is to minimize abandonment: the number of rounds with no clicks.

Slivkins et al. 2013 study an extension in which metric similarity information is available. They consider a version with stochastic payoffs: in each round, the user vector is an independent sample from a fixed distribution, and assume a Lipschitz-style condition that connects expected clicks with the metric space. They run a separate bandit algorithm (e.g., contextual zooming) for each of the $k$ “slots” in the ranking. Without loss of generality, in each round the documents are selected sequentially, in the top-down order. Since a document in slot $i$ is clicked in a given round only if all higher ranked documents are not relevant, they treat the set of documents in the higher slots as a context for the $i$-th algorithm. The Lipschitz-style condition on expected clicks suffices to guarantee the corresponding Lipschitz-style condition on contexts.

Bandits with stochastically evolving payoffs: missing proofs

We prove Corollary 6.3 and Corollary 6.4 which address the performance of contextual zooming for the stochastically evolving payoffs. In each corollary we bound from above the average dynamic regret $\hat{R}(T)$ of contextual zooming with period $T_{0}$, for any $T\geq T_{0}$. Since $\hat{R}(T)\leq 2\hat{R}(T_{0})$, it suffices to bound $\hat{R}(T_{0})$, which is the same as $\hat{R}(T_{0})$ for (non-periodic) contextual zooming. Therefore, we can focus on analyzing the non-periodic algorithm.

We start with two simple auxiliary claims.

Consider the contextual MAB problem with a product similarity space. Let $\Delta(x,y)\triangleq\mu^{*}(x)-\mu(x,y)$ be the “badness” of point $(x,y)$ in the similarity space. Then