Multi-Armed Bandits in Metric Spaces

Introduction

In a multi-armed bandit problem, an online algorithm must choose from a set of strategies in a sequence of $n$ trials so as to maximize the total payoff of the chosen strategies. These problems are the principal theoretical tool for modeling the exploration/exploitation tradeoffs inherent in sequential decision-making under uncertainty. Studied intensively for the last three decades , bandit problems are having an increasingly visible impact on computer science because of their diverse applications including online auctions, adaptive routing, and the theory of learning in games. The performance of a multi-armed bandit algorithm is often evaluated in terms of its regret, defined as the gap between the expected payoff of the algorithm and that of an optimal strategy. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with exponentially or infinitely large strategy sets are still a topic of very active investigation .

Absent any assumptions about the strategies and their payoffs, bandit problems with large strategy sets allow for no non-trivial solutions — any multi-armed bandit algorithm performs as badly, on some inputs, as random guessing. But in most applications it is natural to assume a structured class of payoff functions, which often enables the design of efficient learning algorithms . In this paper, we consider a broad and natural class of problems in which the structure is induced by a metric on the space of strategies. While bandit problems have been studied in a few specific metric spaces (such as a one-dimensional interval) , the case of general metric spaces has not been treated before, despite being an extremely natural setting for bandit problems. As a motivating example, consider the problem faced by a website choosing from a database of thousands of banner ads to display to users, with the aim of maximizing the click-through rate of the ads displayed by matching ads to users’ characterizations and the web content that they are currently watching. Independently experimenting with each advertisement is infeasible, or at least highly inefficient, since the number of ads is too large. Instead, the advertisements are usually organized into a taxonomy based on metadata (such as the category of product being advertised) which allows a similarity measure to be defined. The website can then attempt to optimize its learning algorithm by generalizing from experiments with one ad to make inferences about the performance of similar ads . Abstractly, we have a bandit problem of the following form: there is a strategy set $X$, with an unknown payoff function $\mu\,:\,X\rightarrow$ satisfying a set of predefined constraints of the form $|\mu(u)-\mu(v)|\leq\delta(u,v)$ for some $u,v\in X$ and $\delta(u,v)>0$. In each period the algorithm chooses a point $x\in X$ and observes an independent random sample from a payoff distribution whose expectation is $\mu(x)$.

A moment’s thought reveals that this abstract problem can be regarded as a bandit problem in a metric space. Specifically, if $L(u,v)$ is defined to be the infimum, over all finite sequences $u=x_{0},x_{1},\ldots,x_{k}=v$ in $X$, of the quantity $\sum_{i}\delta(x_{i},x_{i+1})$, then $L$ is a metricMore precisely, it is a pseudometric because some pairs of distinct points $x,y\in X$ may satisfy $L(x,y)=0$. and the constraints $|\mu(u)-\mu(v)|<\delta(u,v)$ may be summarized by stating that $\mu$ is a Lipschitz function (of Lipschitz constant $1$) on the metric space $(L,X)$. We refer to this problem as the Lipschitz MAB problem on $(L,X)$, and we refer to the ordered triple $(L,X,\mu)$ as an instance of the Lipschitz MAB problem. When the metric space $(L,X)$ is understood from context, we may also refer to $\mu$ as an instance.

While our work is the first to treat the Lipschitz MAB problem in general metric spaces, special cases of the problem are implicit in prior work on the continuum-armed bandit problem — which corresponds to the space $$under the metric$L_{d}(x,y)=|x-y|^{1/d}$,$d\geq 1$— and the experimental work on “bandits for taxonomies” , which corresponds to the case in which$(L,X)$is a tree metric. Before describing our results in greater detail, it is helpful to put them in context by recounting the nearly optimal bounds for the one-dimensional continuum-armed bandit problem, a problem first formulated by R. Agrawal in 1995 and recently solved (up to logarithmic factors) by various authors . In the following theorem and throughout this paper, the regret of a multi-armed bandit algorithm$\mathcal{A}$running on an instance$(L,X,\mu)$is defined to be the function$R_{\mathcal{A}}(t)$which measures the difference between its expected payoff at time$t$and the quantity$t\,\sup_{x\in X}\mu(x)$. The latter quantity is the expected payoff of always playing a strategy$x\in\operatornamewithlimits{argmax}\mu(x)$ if such strategy exists.

In fact, if the time horizon $t$ is known in advance, the upper bound in the theorem can be achieved by an extremely naïve algorithm which simply uses an optimal $k$-armed bandit algorithm (such as the ucb1 algorithm ) to choose strategies from the set $S=\{0,\tfrac{1}{k},\,\tfrac{2}{k},\,\ldots,1\}$, for a suitable choice of the parameter $k$. While the regret bound in Theorem 1.1 is essentially optimal for the Lipschitz MAB problem in $(L_{d},)$, it is strikingly odd that it is achieved by such a simple algorithm. In particular, the algorithm approximates the strategy set by a fixed mesh $S$ and does not refine this mesh as it gains information about the location of the optimal strategy. Moreover, the metric contains seemingly useful proximity information, but the algorithm ignores this information after choosing its initial mesh. Is this really the best algorithm?

A closer examination of the lower bound proof raises further reasons for suspicion: it is based on a contrived, highly singular payoff function $\mu$ that alternates between being constant on some distance scales and being very steep on other (much smaller) distance scales, to create a multi-scale “needle in haystack” phenomenon which nearly obliterates the usefulness of the proximity information contained in the metric $L_{d}$. Can we expect algorithms to do better when the payoff function is more benign? For the Lipschitz MAB problem on $(L_{1},)$, the question was answered affirmatively in for some classes of instances, with algorithms that are tuned to the specific classes.

Our results and techniques.

In this paper we consider the Lipschitz MAB problem on arbitrary metric spaces. We are concerned with the following two main questions motivated by the discussion above:

What is the best possible bound on regret for a given metric space?

Can one take advantage of benign payoff functions?

In this paper we give a complete solution to (i), by describing for every metric space $X$ a family of algorithms which come arbitrarily close to achieving the best possible regret bound for $X$. We also give a satisfactory answer to (ii); our solution is arbitrarily close to optimal in terms of the zooming dimension defined below. In fact, our algorithm for (i) is an extension of the algorithmic technique used to solve (ii).

Our main technical contribution is a new algorithm, the zooming algorithm, that combines the upper confidence bound technique used in earlier bandit algorithms such as ucb1 with a novel adaptive refinement step that uses past history to zoom in on regions near the apparent maxima of $\mu$ and to explore a denser mesh of strategies in these regions. This algorithm is a key ingredient in our design of an optimal bandit algorithm for every metric space $(L,X)$. Moreover, we show that the zooming algorithm can perform significantly better on benign problem instances. That is, for every instance $(L,X,\mu)$ we define a parameter called the zooming dimension, and use it to bound the algorithm’s performance in a way that is often significantly stronger than the corresponding per-metric bound. Note that the zooming algorithm is self-tuning, i.e. it achieves this bound without requiring prior knowledge of the zooming dimension.

To state our theorem on the per-metric optimal solution for (i), we need to sketch a few definitions which arise naturally as one tries to extend the lower bound from to general metric spaces. Let us say that a subset $Y$ in a metric space $X$ has covering dimension $d$ if it can be covered by $O(\delta^{-d})$ sets of diameter $\delta$ for all $\delta>0$. A point $x\in X$ has local covering dimension $d$ if it has an open neighborhood of covering dimension $d$. The space $X$ has max-min-covering dimension $d=\mathtt{MaxMinCOV}(X)$ if it has no subspace whose local covering dimension is uniformly bounded below by a number greater than $d$.

Consider the Lipschitz MAB problem on a compact metric space $(L,X)$. Let $d=\mathtt{MaxMinCOV}(X)$. If $\gamma>\tfrac{d+1}{d+2}$ then there exists a bandit algorithm $\mathcal{A}$ such that for every problem instance $\mathcal{I}$ it satisfies $R_{\mathcal{A}}(t)=O_{\mathcal{I}}(t^{\gamma})$ for all $t$. No such algorithm exists if $d>0$ and $\gamma<\tfrac{d+1}{d+2}$.

In general $\mathtt{MaxMinCOV}(X)$ is bounded above by the covering dimension of $X$. For metric spaces which are highly homogeneous (in the sense that any two $\epsilon$-balls are isometric to one another) the two dimensions are equal, and the upper bound in the theorem can be achieved using a generalization of the naïve algorithm described earlier. The difficulty in Theorem 1.2 lies in dealing with inhomogeneities in the metric space.To appreciate this issue, it is very instructive to consider a concrete example of a metric space $(L,X)$ where $\mathtt{MaxMinCOV}(X)$ is strictly less than the covering dimension, and for this specific example design a bandit algorithm whose regret bounds are better than those suggested by the covering dimension. This is further discussed in Section 3. It is important to treat the problem at this level of generality, because some of the most natural applications of the Lipschitz MAB problem, e.g. the web advertising problem described earlier, are based on highly inhomogeneous metric spaces. (That is, in web taxonomies, it is unreasonable to expect different categories at the same level of a topic hierarchy to have the roughly the same number of descendants.)

The algorithm in Theorem 1.2 combines the zooming algorithm described earlier with a delicate transfinite construction over closed subsets consisting of “fat points” whose local covering dimension exceeds a given threshold $d$. For the lower bound, we craft a new dimensionality notion, the max-min-covering dimension introduced above, which captures the inhomogeneity of a metric space, and we connect this notion with the transfinite construction that underlies the algorithm.

For “benign” input instances we provide a better performance guarantee for the zooming algorithm. The lower bounds in Theorems 1.1 and 1.2 are based on contrived, highly singular, “needle in haystack” instances in which the set of near-optimal strategies is astronomically larger than the set of precisely optimal strategies. Accordingly, we quantify the tractability of a problem instance in terms of the number of near-optimal strategies. We define the zooming dimension of an instance $(L,X,\mu)$ as the smallest $d$ such that the following covering property holds: for every $\delta>0$ we require only $O(\delta^{-d})$ sets of diameter $\delta/8$ to cover the set of strategies whose payoff falls short of the maximum by an amount between $\delta$ and $2\delta$.

The zooming dimension can be significantly smaller than the max-min-covering dimension. Let us illustrate this point with two examples (where for simplicity the max-min-covering dimension is equal to the covering dimension). For the first example, consider a metric space consisting of a high-dimensional part and a low-dimensional part. For concreteness, consider a rooted tree $T$ with two top-level branches $T^{\prime}$ and $T^{\prime\prime}$ which are complete infinite $k$-ary trees, $k=2,10$. Assign edge weights in $T$ that are exponentially decreasing with distance to the root, and let $L$ be the resulting shortest-path metric on the leaf set $X$.Here a leaf is defined as an infinite path away from the root. If there is a unique optimal strategy that lies in the low-dimensional part $T^{\prime}$ then the zooming dimension is bounded above by the covering dimension of $T^{\prime}$, whereas the “global” covering dimension is that of $T^{\prime\prime}$. In the second example, let $(L,X)$ be a homogeneous high-dimensional metric, e.g. the Euclidean metric on the unit $k$-cube, and the payoff function is $\mu(x)=1-L(x,S)$ for some subset $S$. Then the zooming dimension is equal to the covering dimension of $S$, e.g. it is if $S$ is a finite point set.

Discussion.

In stating the theorems above, we have been imprecise about specifying the model of computation. In particular, we have ignored the thorny issue of how to provide an algorithm with an input containing a metric space which may have an infinite number of points. The simplest way to interpret our theorems is to ignore implementation details and interpret “algorithm” to mean an abstract decision rule, i.e. a (possibly randomized) function mapping a history of past observations $(x_{i},r_{i})\in X\times$ to a strategy $x\in X$ which is played in the current period. All of our theorems are valid under this interpretation, but they can also be made into precise algorithmic results provided that the algorithm is given appropriate oracle access to the metric space. In most cases, our algorithms require only a covering oracle which takes a finite collection of open balls and either declares that they cover $X$ or outputs an uncovered point. We refer to this setting as the standard Lipschitz MAB problem. For example, the zooming algorithm uses only a covering oracle for $(L,X)$, and requires only one oracle query per round (with at most $t$ balls in round $t$). However, the per-metric optimal algorithm in Theorem 1.2 uses more complicated oracles, and we defer the definition of these oracles to Section 3.

While our definitions and results so far have been tailored for the Lipschitz MAB problem on infinite metrics, some of them can be extended to the finite case as well. In particular, for the zooming algorithm we obtain sharp results (that are meaningful for both finite and infinite metrics) using a more precise, non-asymptotic version of the zooming dimension. Extending the notions in Theorem 1.2 to the finite case is an open question.

Extensions.

We provide a number of extensions in which we elaborate on our analysis of the zooming algorithm. First, we provide sharper bounds for several examples in which the reward from playing each strategy $u$ is $\mu(u)$ plus an independent noise of a known and “benign” shape. Second, we upgrade the zooming algorithm so that it satisfies the guarantee in Theorem 1.3 and enjoys a better guarantee if the maximal reward is exactly 1. Third, we apply this result to a version where $\mu(\cdot)=1-L(\,\cdot\,,S)$ for some target set $S$ which is not revealed to the algorithm. Fourth, we relax some assumptions in the analysis of the zooming algorithm, and use this generalization to analyze the version in which $\mu(\cdot)=1-f(L(\,\cdot\,,S))$ for some known function $f$. Finally, we extend our analysis from reward distributions supported on $$ to those with unbounded support and finite absolute third moment.

Follow-up work.

For metric spaces whose max-min-covering dimension is exactly 0, this paper provides an upper bound $R(T)=O_{\mathcal{I}}(T^{\gamma})$ for any $\gamma>\tfrac{1}{2}$, but no matching lower bound. Characterizing the optimal regret for such metric spaces remained an open question. Following the publication of the conference version, this question has been settled in , revealing the following dichotomy: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in\omega(\log t)$, or bounded below by any $g\in o(\sqrt{T})$, depending on whether the completion of the metric space is compact and countable.

1 Preliminaries

Given a metric space, $B(x,r)$ denotes an open ball of radius $r$ around point $x$. Throughout the paper, he constants in the $O(\cdot)$ notation are absolute unless specified otherwise.

In the Lipschitz MAB problem on $(L,X)$, there is a strategy set $X$, a metric space $(L,X)$ of diameter $\leq 1$, and a payoff function $\mu\,:\,X\rightarrow$ such that the following Lipschitz condition holds:

Call $L$ is the similarity function. The metric space $(L,X)$ is revealed to an algorithm, whereas the payoff function $\mu$ is not. In each round the algorithm chooses a strategy $x\in X$ and observes an independent random sample from a payoff distribution $\mathcal{D}(x)$ with support $\mathcal{S}\subset$ and expectation $\mu(x)$.

The regret of a bandit algorithm $\mathcal{A}$ running on a given problem instance is $R_{\mathcal{A}}(t)=W_{\mathcal{A}}(t)-t\mu^{*}$, where $W_{\mathcal{A}}(t)$ is the expected payoff of $\mathcal{A}$ at time $t$ and $\mu^{*}=\sup_{x\in X}\mu(x)$ is the maximal expected reward.

The $C$-zooming dimension of the problem instance $(L,X,\mu)$ is the smallest $d$ such that for every $r\in(0,1]$ the set $X_{r}=\{x\in X:\,\tfrac{r}{2}<\mu^{*}-\mu(x)\leq r\}$ can be covered by $C\,r^{-d}$ sets of diameter at most $r/8$.

Fix a metric space on set $X$. Let $N(r)$ be the smallest number of sets of diameter $r$ required to cover $X$. The covering dimension of $X$ is

The $c$-covering dimension of $X$ is defined as the infimum of all $d$ such that $N(r)\leq cr^{-d}$ for all $r>0$.

In Section 2 we prove Theorem 1.3. In Section 3 we discuss the per-metric optimality and prove Theorem 1.2. Section 4 covers the extensions.

Adaptive exploration: the zooming algorithm

In this section we introduce the zooming algorithm which uses adaptive exploration to take advantage of the ”benign” input instances, and prove the main guarantee (Theorem 1.3).

Consider the standard Lipschitz MAB problem on $(L,X)$. The zooming algorithm proceeds in phases $i=1,2,3,\ldots$ of $2^{i}$ rounds each. Let us consider a single phase $i_{\mathtt{ph}}$ of the algorithm. For each strategy $v\in X$ and time $t$, let $n_{t}(v)$ be the number of times this strategy has been played in this phase before time $t$, and let $\mu_{t}(v)$ be the corresponding average reward. Define $\mu_{t}(v)=0$ if $n_{t}(v)=0$. Note that at time $t$ both quantities are known to the algorithm. Define the confidence radius of $v$ at time $t$ as

Let $\mu(v)$ be the expected reward of strategy $v$. Note that $E[\mu_{t}(v)]=\mu(v)$. Using Chernoff Bounds, we can bound $|\mu_{t}(v)-\mu(v)|$ in terms of the confidence radius:

A phase is called clean if for each strategy $v\in X$ that has been played at least once during this phase and each time $t$ we have $|\mu_{t}(v)-\mu(v)|\leq r_{t}(v)$.

Phase $i_{\mathtt{ph}}$ is clean with probability at least $1-4^{-i_{\mathtt{ph}}}$.

Throughout the execution of the algorithm, a finite number of strategies are designated active. Our algorithm only plays active strategies, among which it chooses a strategy $v$ with the maximal index

Say that strategy $v$ covers strategy $u$ at time $t$ if $u\in B(v,\,r_{t}(v))$. Say that a strategy $u$ is covered at time $t$ if at this time it is covered by some active strategy $v$. Note that the covering oracle (as defined in Section 1) can return a strategy which is not covered if such strategy exists, or else inform the algorithm that all strategies are covered. Now we are ready to state the algorithm:

Each phase $i$ runs for $2^{i}$ rounds. In the beginning of the phase no strategies are active. In each round do the following:

If some strategy is not covered, make it active.

Play an active strategy with the maximal index (3); break ties arbitrarily.

We formulate the main result of this section as follows:

Consider the standard Lipschitz MAB problem. Let $\mathcal{A}$ be Algorithm 2.3. Then $\forall\,C>0$

where $d$ is the $C$-zooming dimension of the problem instance.

The zooming algorithm is not parameterized by the $C$ in (4), yet satisfies (4) for all $C>0$. For sharper guarantees, $C$ can be tuned to the specific problem instance and specific time $t$.

Let us prove Theorem 2.4. Note that after step 1 in Algorithm 2.3 all strategies are covered. (Indeed, if some strategy is activated in step 1 then it covers the entire metric.) Let $\mu^{*}=\sup_{u\in X}\mu(u)$ be the maximal expected reward; note that we do not assume that the supremum is achieved by some strategy. Let $\Delta(v)=\mu^{*}-\mu(v)$. Let us focus on a given phase $i_{\mathtt{ph}}$ of the algorithm.

If phase $i_{\mathtt{ph}}$ is clean then we have $\Delta(v)\leq 4\,r_{t}(v)$ for any time $t$ and any strategy $v$. It follows that $n_{t}(v)\leq O(i_{\mathtt{ph}})\,\Delta^{-2}(v)$.

Suppose strategy $v$ is played at time $t$. First we claim that $I_{t}(v)\geq\mu^{*}$. Indeed, fix $\epsilon>0$. By definition of $\mu^{*}$ there exists a strategy $v^{*}$ such that $\Delta(v^{*})<\epsilon$. Let $v_{t}$ be an active strategy that covers $v^{*}$. By the algorithm specification $I_{t}(v)\geq I_{t}(v_{t})$. Since $v$ is clean at time $t$, by definition of index we have $I_{t}(v_{t})\geq\mu(v_{t})+r_{t}(v_{t})$. By the Lipschitz property we have $\mu(v_{t})\geq\mu(v^{*})-L(v_{t},v^{*})$. Since $v_{t}$ covers $v^{*}$, we have $L(v_{t},v^{*})\leq r_{t}(v_{t})$ Putting all these inequalities together, we have $I_{t}(v)\geq\mu(v^{*})\geq\mu^{*}-\epsilon$. Since this inequality holds for an arbitrary $\epsilon>0$, we in fact have $I_{t}(v)\geq\mu^{*}$. Claim proved.

Furthermore, note that by the definitions of “clean phase” and “index” we have $\mu^{*}\leq I_{t}(v)\leq\mu(v)+3\,r_{t}(v)$ and therefore $\Delta(v)\leq 3\,r_{t}(v)$.

Now suppose strategy $v$ is not played at time $t$. If it has never been played before time $t$ in this phase, then $r_{t}(v)>1$ and thus the lemma is trivial. Else, let $s$ be the last time strategy $v$ has been played before time $t$. Then by definition of the confidence radius $r_{t}(v)=r_{s+1}(v)\geq\sqrt{2/3}\,r_{s}(v)\geq\tfrac{1}{4}\,\Delta(v)$. ∎

In a clean phase, for any active strategies $u,v$ we have $L(u,v)>\tfrac{1}{4}\min(\Delta(u),\Delta(v))$.

Assume $u$ has been activated before $v$. Let $s$ be the time when $v$ has been activated. Then by the algorithm specification we have $L(u,v)>r_{s}(u)$. By Lemma 2.5 $r_{s}(u)\geq\tfrac{1}{4}\Delta(u)$. ∎

Let $d$ be the the $C$-zooming dimension. For a given time $t$ in the current phase, let $S(t)$ be the set of all strategies that are active at time $t$, and let

We claim that $|A(i,t)|\leq C\,2^{id}$. Indeed, set $A(i,t)$ can be covered by $C\,2^{id}$ sets of diameter at most $2^{-i}/8$; by Corollary 2.6 each of these sets contains at most one strategy from $A(i,t)$.

In a clean phase $i_{\mathtt{ph}}$, for each time $t$ we have

where $\gamma=\tfrac{d+1}{d+2}$ and $d$ is the $C$-zooming dimension.

Fix the time horizon $t$. For a subset $S\subset X$ of strategies, let $R_{S}=\sum_{v\in S}\Delta(v)\,n_{t}(v)$. Let us choose $\rho\in(0,1)$ such that

Define $B$ as the set of all strategies $v\in S(t)$ such that $\Delta(v)\leq\rho$. Recall that by Lemma 2.5 for each $v\in A(i,t)$ we have $n_{t}(v)\leq O(i_{\mathtt{ph}})\,\Delta^{-2}(v)$. Then

The left-hand side of (5) is essentially the contribution of the current phase to the overall regret. It remains to sum these contributions over all past phases.

Let $i_{\mathtt{ph}}$ be the current phase, let $t$ be the time spend in this phase, and let $T$ be the total time since the beginning of phase $1$. Let $R_{\mathtt{ph}}(i_{\mathtt{ph}},t)$ be the left-hand side of (5). Combining Claim 2.2 and Claim 2.7, we have

Attaining the optimal per-metric performance

In this section we ask, “What is the best possible algorithm for the Lipschitz MAB problem on a given metric space?” We consider the per-metric performance, which we define as the worst-case performance of a given algorithm over all possible problem instances on a given metric. As everywhere else in this paper, we focus on minimizing the exponent $\gamma$ such that $R_{\mathcal{A}}(t)\leq t^{\gamma}$ for all sufficiently large $t$. Motivated by the shape of the guarantees in Theorem 1.1, let us define the regret dimension of an algorithm as follows.

Consider the Lipschitz MAB problem on a given metric space. For algorithm $\mathcal{A}$ and problem instance $\mathcal{I}$ let

The regret dimension of $\mathcal{A}$ is $\mathtt{DIM}(\mathcal{A})=\sup_{\mathcal{I}}\,\mathtt{DIM}_{\mathcal{I}}(\mathcal{A})$, where the supremum is taken over all problem instances $\mathcal{I}$ on the given metric space.

Then Theorem 1.1 states that for the Lipschitz MAB problem on $(L_{d},)$, the regret dimension of the “naïve algorithm” is at most $d$. In fact, it is easy to extend the “naïve algorithm” to arbitrary metric spaces. Such algorithm is parameterized by the covering dimension $d$ of the metric space. It divides time into phases of exponentially increasing length, chooses a $\delta$-net during each phase,It is easy to see that the cardinality of this $\delta$-net is $K=O(\delta^{-d})$. and runs a $K$-armed bandit algorithm such as ucb1 on the elements of the $\delta$-net. The parameter $\delta$ is tuned optimally given $d$ and the phase length $T$; the optimal value turns out to be $\delta=T^{-1/(d+2)}$. Using the technique from it is easy to prove that the regret dimension of this algorithm is at most $d$.

Consider the Lipschitz MAB problem on a metric space $(L,X)$ of covering dimension $d$. Let $\mathcal{A}$ be the naïve algorithm that uses ucb1 in each phase. Then $\mathtt{DIM}(\mathcal{A})\leq d$.

Let us focus on some phase $i$. In this phase the algorithm chooses a $\delta$-net, call it $S$. We claim that $|S|\leq c\,\delta^{-d}$. Indeed, for any $\delta^{\prime}<\delta$ the metric space can be covered by $c\,\delta^{-d}$ sets of diameter at most $\delta^{\prime}$, each of which can contain only one point from $S$. Claim proved. The algorithm proceeds to run ucb1 on the elements of $S$. By the expected regret of ucb1 on $K$ arms in $t$ rounds is at most $O(\sqrt{K\,t\log t})$. Since the maximal $\mu$ on $S$ is at most $\delta$ off of the maximal $\mu$ on $X$, we have

Thus we ask: is it possible to achieve a better regret dimension, perhaps using a more sophisticated algorithm? We show that this is indeed the case. Moreover, we provide an algorithm such that for any given metric space its regret dimension is arbitrarily close to optimal.

The rest of this section is organized as follows. In Section 3.1 we develop a lower bound on regret dimension. In Section 3.2 we will show that for some metric spaces, there exist algorithms whose regret dimension is smaller than the covering dimension. We develop these ideas further in Section 3.3 and provide an algorithm whose regret dimension is arbitrarily close to optimal.

Let us develop a lower bound on regret dimension of any algorithm on a given metric space. This bound is equal to the covering dimension for highly homogeneous metric spaces (such as those in which all balls of a given radius are isometric to each other), but in general it can be much smaller.

It is known that a worst-case instance of the $K$-armed bandit problem consists of $K-1$ strategies with identical payoff distributions, and one which is slightly better. We refer to this as a “needle-in-haystack” instance. The known constructions of lower bounds for Lipschitz MAB problems rely on creating a multi-scale needle-in-haystack instance in which there are $K$ disjoint open sets, and $K-1$ of them consist of strategies with identical payoff distributions, but in the remaining open set there are strategies whose payoff is slightly better. Moreover, this special open set contains $K^{\prime}\gg K$ disjoint subsets, only one of which contains strategies superior to the others, and so on down through infinitely many levels of recursion. To ensure that this construction can be continued indefinitely, one needs to assume a covering property which ensures that each of the open sets arising in the construction has sufficiently many disjoint subsets to continue to the next level of recursion.

For a metric space $(L,X)$, we say that $d$ is the min-covering dimension of $X$, $d=\mathtt{MinCOV}(X)$, if $d$ is the infimum of $\mathtt{COV}(U)$ over all non-empty open subsets $U\subseteq X$. The max-min-covering dimension of $X$ is defined by

The infimum over open $U\subseteq X$ in the definition of min-covering dimension ensures that every open set which may arise in the needle-in-haystack construction described above will contain $\Omega(\delta^{\varepsilon-d})$ disjoint $\delta$-balls for some sufficiently small $\delta,\varepsilon$. Constructing lower bounds for Lipschitz MAB algorithms in a metric space $X$ only requires that $X$ should have subsets with large min-covering dimension, which explains the supremum over subsets in the definition of max-min-covering dimension.

We will use the following simple packing lemma.This is a folklore result; we provide the proof for convenience.

If $Y$ is a metric space of covering dimension $d$, then for any $b<d$ and $r_{0}>0$, there exists $r\in(0,r_{0})$ such that $Y$ contains a collection of at least $r^{-b}$ disjoint open balls of radius $r$.

Let $r<r_{0}$ be a positive number such that every covering of $Y$ requires more than $r^{-b}$ balls of radius $2r$. Such an $r$ exists, because the covering dimension of $Y$ is strictly greater than $b$. Now let $\mathcal{P}=\{B_{1},B_{2},\ldots,B_{M}\}$ be any maximal collection of disjoint $r$-balls. For every $y\in Y$ there must exist some ball $B_{i}\;(1\leq i\leq M)$ whose center is within distance $2r$ of $y$, as otherwise $B(y,r)$ would be disjoint from every element of $\mathcal{P}$ contradicting the maximality of that collection. If we enlarge each ball $B_{i}$ to a ball $B_{i}^{+}$ of radius $2r$, then every $y\in Y$ is contained in one of the balls $\{B_{i}^{+}\,|\,1\leq i\leq M\}$, i.e. they form a covering of $Y$. Hence $M\geq r^{-b}$ as desired. ∎

If $X$ is a metric space and $d$ is the max-min-covering dimension of $X$ then $\mathtt{DIM}(\mathcal{A})\geq d$ for every bandit algorithm $\mathcal{A}$.

Without loss of generality let us assume that $d>0$. Given $\gamma<\tfrac{d+1}{d+2},$ let $a<b<c<d$ be such that $\gamma<\tfrac{a+1}{a+2}$. Let $Y$ be a subset of $X$ such that $\mathtt{MinCOV}(Y)\geq c$. Using Lemma 3.4 we recursively construct an infinite sequence of sets $\mathcal{P}_{0},\mathcal{P}_{1},\ldots$ each consisting of finitely many disjoint open balls in $X$, centered at points of $Y$. Let $\mathcal{P}_{0}=\{X\}$ consist of a single ball that contains all of $X$. If $i>0$, for every ball $B\in\mathcal{P}_{i-1}$, let $r$ denote the radius of $B$ and choose a number $r_{i}(B)\in(0,r/4)$ such that $B$ contains $n_{i}(B)=\lceil r_{i}(B)^{-b}\rceil$ disjoint balls of radius $r_{i}(B)$ centered at points of $Y$. Such a collection of disjoint balls exists, by Lemma 3.4. Let $\mathcal{P}_{i}(B)$ denote this collection of disjoint balls and let $\mathcal{P}_{i}=\bigcup_{B\in\mathcal{P}_{i-1}}\mathcal{P}_{i}(B).$ Now sample a random sequence of balls $B_{1},B_{2},\ldots$ by picking $B_{1}\in\mathcal{P}_{1}$ uniformly at random, and for $i>1$ picking $B_{i}\in\mathcal{P}_{i}(B_{i-1})$ uniformly at random.

Given a ball $B=B(x_{*},r_{*})$, let $f_{B}(x)$ be a Lipschitz function on $X$ defined by

Let $f_{i}=f_{B_{i}}$ for $i\geq 1$. Define $f_{0}$ by setting $f_{0}(x)=1/3$ for all $x\in X$. The reader may verify that the sum $\mu=\sum_{i=0}^{\infty}f_{i}$ is a Lipschitz function. Define the payoff distribution for $x\in X$ to be a Bernoulli random variable with expectation $\mu(x)$. We have thus specified a randomized construction of an instance $(L,X,\mu)$.

We claim that for any algorithm $\mathcal{A}$ and any constant $C$,

The proof of this claim is based on a “needle in haystack” lemma (Lemma 3.6 below) which states that for all $i$, conditional on the sequence $B_{1},\ldots,B_{i-1}$, with probability at least $1-O((r_{i}(B_{i}))^{(b-a)/2})$, no more than half of the first $t_{i}(B_{i})=r_{i}(B_{i})^{-a-2}$ strategies picked by $\mathcal{A}$ lie inside $B_{i}$. The proof of the lemma is deferred to the end of this section.

Any strategy $x\not\in B_{i}$ satisfies $\mu(x)<\mu(x^{*})-r_{i}/2$, so we may conclude that

Denoting $r_{i}(B_{i})$ and $t_{i}(B_{i})$ by $r_{i}$ and $t_{i}$, respectively, we have $\tfrac{1}{4}\,r_{i}^{-a-1}=\tfrac{1}{4}\,t_{i}^{(a+1)/(a+2)}>Ct_{i}^{\gamma}$ for all sufficiently large $i$. As $i$ runs through the positive integers, the terms on the right side of (8) are dominated by a geometric progression because $r_{i}(B_{i})\leq 4^{-i}.$ By the Borel-Cantelli Lemma, almost surely there are only finitely many $i$ such that the events on the left side of (8) occur. Thus (7) follows. ∎

To prove Theorem 3.5 it suffices to show that for every given algorithm there exists a “hard” problem instance. In fact we proved a stronger result (7): essentially, we construct a probability distribution over problem instances which is hard, almost surely, for every given algorithm. This seems to be the best possible bound since, obviously, a single problem instance cannot be hard for every algorithm.

In rest of this subsection we prove the “needle in haystack” lemma used in the proof of Theorem 3.5.

Consider the randomized construction of an instance $(L,X,\mu)$ in the proof of Theorem 3.5. Fix a bandit algorithm $\mathcal{A}$. Then for all $i$, conditional on the sequence $B_{1},\ldots,B_{i-1}$, with probability at least $1-O((r_{i}(B_{i}))^{(b-a)/2})$, no more than half of the first $r_{i}(B_{i})^{-a-2}$ strategies picked by $\mathcal{A}$ lie inside $B_{i}$.

Let us introduce some notation needed to prove the lemma. Let us fix an arbitrary Lipschitz MAB algorithm $\mathcal{A}$. We will assume that $\mathcal{A}$ is deterministic; the corresponding result for randomized algorithms follows by conditioning on the algorithm’s random bits (so that its behavior, conditional on these bits, is deterministic), invoking the lemma for deterministic algorithms, and then removing the conditioning by averaging over the distribution of random bits. Note that since our construction uses only $\{0,1\}$-valued payoffs, and the algorithm $\mathcal{A}$ is deterministic, the entire history of play in the first $t$ rounds can be summarized by a binary vector $\sigma\in\{0,1\}^{t}$, consisting of the payoffs observed by $\mathcal{A}$ in the first $t$ rounds. Thus a payoff function $\mu$ determines a probability distribution $P_{\mu}$ on the set $\{0,1\}^{t}$, i.e. the distribution on $t$-step histories realized when using algorithm $\mathcal{A}$ on instance $\mu$.

Let $B$ be any ball in the set $\mathcal{P}_{i-1}$, let $n=n_{i}(B)$, $r=r_{i}(B)$, and $t=t_{i}(B)=r_{i}(B)^{-a-2}$. Let $B^{1},B^{2},\ldots,B^{n}$ be an enumeration of the balls in $\mathcal{P}_{i}(B)$. Choose an arbitrary sequence of balls $B_{1}\supseteq B_{2}\supseteq\ldots\supseteq B_{i-1}=B$ such that $B_{1}\in\mathcal{P}_{1}$ and for all $j>0$ $B_{j}\in\mathcal{P}(B_{j-1}).$ Similarly, for $k=1,2,\ldots,n$, choose an arbitrary sequence of balls $B^{k}=B^{k}_{i}\supseteq B^{k}_{i+1}\supseteq\ldots$ such that $B^{k}_{j}\in\mathcal{P}(B^{k}_{j-1})$ for all $j\geq i.$ Define functions $f_{j}\;(1\leq j\leq i-1)$ and $f^{k}_{j}\;(j\geq i)$ using the balls $B_{j},B^{k}_{j}$, as in the proof of Theorem 3.5. Specifically, use definition (6) and set $f_{j}=f_{B_{j}}$ and $f^{k}_{j}=f_{B^{k}_{j}}$. Let $\mu^{0}=\sum_{j=0}^{i-1}f_{j}$ and

Note that the instances $\mu^{k}\;(1\leq k\leq n)$ are equiprobable under our distribution on input instances $\mu$. The instance $\mu^{0}$ is not one that could be randomly sampled by our construction, but it is useful as a “reference measure” in the following proof. Note that the functions $\mu^{k}$ have the following properties, by construction.

$1/3\leq\mu^{k}(x)\leq 2/3$ for all $x\in X$.

$0\leq\mu^{k}(x)-\mu^{0}(x)\leq r$ for all $x\in X$.

If $x\in X\setminus B^{k},$ then $\mu^{k}(x)=\mu^{0}(x)$.

If $x\in X\setminus B^{k},$ then there exists some point $x^{k}\in B^{k}$ such that $\mu^{k}(x^{k})-\mu^{k}(x)\geq r/2.$

Each of the payoff functions $\mu^{k}\;(0\leq k\leq n)$ gives rise to a probability distribution $P_{\mu^{k}}$ on $\{0,1\}^{t}$ as described in the preceding section. We will use the shorthand notation $P_{k}$ instead of $P_{\mu^{k}}$. We will also use $\mathbf{E}_{k}$ to denote the expectation of a random variable under distribution $P_{k}$. Finally, we let $N_{k}$ denote the random variable defined on $\{0,1\}^{t}$ that counts the number of rounds $s\;(1\leq s\leq t)$ in which algorithm $\mathcal{A}$ chooses a strategy in $B^{k}$ given the history $\sigma$.

The following lemma is analogous to Lemma A.1 of , and its proof is identical to the proof of that lemma.

Let $f\,:\,\{0,1\}^{t}\rightarrow[0,M]$ be any function defined on reward sequences $\sigma$. Then for any $k$,

Applying Lemma 3.7 with $f=N_{k}$ and $M=t$, and averaging over $k$, we may apply exactly the same reasoning as in the proof of Theorem A.2 of to derive the bound

Recalling that the actual ball $B_{k}$ sampled when randomly constructing $\mu$ in the proof of Theorem 3.5 is a uniform random sample from $B^{1},B^{2},\ldots,B^{n}$, we may write $N_{*}$ to denote the random variable which counts the number of rounds in which the algorithm plays a strategy in $B_{k}$ and the bound (9) implies

Recalling that $t=r^{-a-2}$ and $n=r^{-b}$, we see that the $O(tr\sqrt{t/n})$ term is the dominant term on the right side, and that it is bounded by $O(tr^{(b-a)/2}).$ An application of Markov’s inequality now yields:

2 Beyond the covering dimension

Thus far, we have seen that every metric space $X$ has a bandit algorithm $\mathcal{A}$ such that $\mathtt{DIM}(\mathcal{A})=\mathtt{COV}(X)$ (the naïve algorithm), and we have seen (via the needle-in-haystack construction, Theorem 3.5) that $X$ can never have a bandit algorithm satisfying $\mathtt{DIM}(\mathcal{A})<\mathtt{MaxMinCOV}(X)$. When $\mathtt{COV}(X)\neq\mathtt{MaxMinCOV}(X)$, which of these two bounds is correct, or can they both be wrong?

In both of the metrics described above, the zooming algorithm (Algorithm 2.3) performs poorly when the optimum $x^{*}$ is located inside the fat subset $S$, because it is too burdensome to keep coveringRecall that a strategy $u$ is called covered at time $t$ if for some active strategy $v$ we have $L(u,v)\leq r_{t}(v)$. the profusion of strategies located near $x^{*}$ as the ball containing $x^{*}$ shrinks. An improved algorithm, achieving regret exponent $d$, modifies the zooming algorithm by imposing quotas on the number of active strategies that lie outside $S$. At any given time, some strategies outside $S$ may not be covered; however, it is guaranteed that there exists an optimal strategy which eventually becomes covered and remains covered forever afterward. Intuitively, if some optimal strategy lies in $S$ then imposing a quota on active strategies outside $S$ does not hurt. If no optimal strategy lies in $S$ then all of $S$ gets covered eventually and stays covered thereafter, in which case the uncovered part of the strategy set has low covering dimension and (starting after the time when $S$ becomes permanently covered) no quota is ever exceeded.

This use of quotas extends to the following general setting which abstracts the idea of “fat subsets”:

Fix a metric space $(L,X)$. A closed subset $S\subset X$ is $d$-fat if $\mathtt{COV}(S)\leq d$ and for any open superset $U$ of $S$ we have $\mathtt{COV}(X\setminus U)\leq d$. More generally, a $d$-fat decomposition of depth $k$ is a decreasing sequence $X=S_{0}\supset\ldots\supset S_{k}\supset S_{k+1}=\emptyset$ of closed subsets such that $\mathtt{COV}(S_{k})\leq d$ and $\mathtt{COV}(S_{i}\setminus U)\leq d$ whenever $i\in[k]$ and $U$ is an open superset of $S_{i+1}$.

Let $(L,X)$ be the metric space in either of the two “tree with a fat subset” examples. Then the corresponding “fat subset” $S$ is $d$-fat. For an example of a fat decomposition of depth $k=2$, consider the product metric $(L^{*},X\times X)$ defined by

with a fat decomposition given by $S_{1}=(S\times X)\cup(X\times S)$ and $S_{2}=S\times S$.

When $X$ is a metric space with a $d^{*}$-fat decomposition $\mathcal{D}$, the algorithm described earlier can be modified to achieve regret $O\left(t^{\gamma}\right)$ for any $\gamma>1-1/(d^{*}+2)$, by instituting a separate quota for each subset $S_{i}.$ The algorithm requires access to a $\mathcal{D}$-covering oracle which for a given $i$ and a given finite set of open balls (given by the centers and the radii) either reports that the balls cover $S_{i}$, or returns some strategy in $S_{i}$ which is not covered by the balls. No further knowledge of $\mathcal{D}$ or the metric space is required.

Consider the Lipschitz MAB problem on a fixed compact metric space with a $d^{*}$-fat decomposition $\mathcal{D}$. Then for any $d>d^{*}$ there is an algorithm $\mathcal{A}_{\mathcal{D}}$ such that $\mathtt{DIM}(\mathcal{A}_{\mathcal{D}})\leq d$.

(1) We can relax the compactness assumption in Theorem 3.10: instead, we can assume that the completion of the metric space is compact and re-define the sets in the $d$-fat decomposition as subsets of the completion (possibly disjoint with the strategy set). This corresponds to the “fat leaf” which lies outside the strategy set. Such extension requires some minor modifications.

(2) The per-metric guarantee expressed by Theorem 3.10 can be complemented with sharper per-instance guarantees. First, for every problem instance $\mathcal{I}$ the per-instance regret dimension $\mathtt{DIM}_{\mathcal{I}}(\mathcal{A})$ is upper-bounded by the zooming dimension of $\mathcal{I}$. Second, if for some $c>0$ the $c$-covering dimension of $X$ is finite then for some $\gamma<1$ and all $t$ we have $R_{\mathcal{A}}(t)\leq O(c\,t^{\gamma})$. However, as this extension is tangential to our main storyline, we focus on analyzing the regret dimension.

Our algorithm proceeds in phases $i=1,2,3,\,\ldots\;$ of $2^{i}$ rounds each. In a given phase, we run a fresh instance of the following phase algorithm $\mathcal{A}_{\mathtt{ph}}(T,d,\mathcal{D})$ parameterized by the phase length $T=2^{i}$, target dimension $d>d^{*}$ and the $\mathcal{D}$-covering oracle. The phase algorithm is a version of a single phase of the zooming algorithm (Algorithm 2.3) with very different rules for activating strategies. As in Algorithm 2.3, the confidence radius and the index are defined by (2) and (3), respectively. At the start of each round some strategies are activated, and then an active strategy with the maximal index is played.

where $\rho=T^{-1/(d+2)}$ and $C_{\rho}=(64k\,\log\tfrac{1}{\rho})^{-1}$. In the beginning of each round the following activation routine is performed. If there exists a set $S_{i}$ such that some strategy in $S_{i}$ is not covered and there is room under the corresponding quota $Q_{i}$, pick one such strategy, activate it, and add it to the corresponding pool $P_{i}$. Since for a given strategy $u$ the confidence radius $r_{t}(u)$ is non-increasing in $t$, the constraint (10) is never violated. Repeat until there are no such sets $S_{i}$ left. This completes the description of the algorithm.

Analysis.

As was the case in Section 2, the analysis of the unbounded-time-horizon algorithm reduces to proving a lemma about the regret of each phase algorithm.

Fix a problem instance in the setting of Theorem 3.10. Let $\mathcal{A}_{\mathtt{ph}}(T)=\mathcal{A}_{\mathtt{ph}}(T,d,\mathcal{D})$. Then

Note that the lemma bounds the regret of $\mathcal{A}_{\mathtt{ph}}(T)$ for time $T\geq t_{\text{min}}$ only. Proving Theorem 3.10 is now straightforward:

Let $\mathcal{A}_{\mathtt{ph}}(T)$ be the phase algorithm from Lemma 3.11. Recall that in each phase $i$ in the overall algorithm $\mathcal{A}$ we simply run a fresh instance of algorithm $\mathcal{A}_{\mathtt{ph}}(2^{i})$ for $2^{i}$ steps.

Let $t_{0}$ be the $t_{\text{min}}$ from (11) rounded up to the nearest end-of-phase time. Let $i_{0}$ be the phase starting at time $t_{0}+1$. Note that $R_{\mathcal{A}}(t_{0})\leq t_{0}$. Let $R_{i}$ be the regret accumulated by $\mathcal{A}$ during phase $i$. Let $\gamma=\tfrac{d+1}{d+2}$. Then for any time $t\geq t_{0}^{1/\gamma}$ in phase $i$ we have $R_{\mathcal{A}}(t)\leq t_{0}+\sum_{j=i_{0}}^{i}R_{j}\leq t_{0}+\sum_{j=i_{0}}^{i}(2^{j})^{\gamma}\leq O(t^{\gamma}).$ ∎

In the remainder of this section we prove Lemma 3.11. Let us fix a problem instance of the Lipschitz MAB problem on a compact metric space $(L,X)$ with a depth-$k$ $d^{*}$-fat decomposition $\mathcal{D}=\{S_{i}\}_{i=0}^{k+1}$. Fix $d>d^{*}$ and let $\mathcal{A}_{\mathtt{ph}}(T)=\mathcal{A}_{\mathtt{ph}}(T,d,\mathcal{D})$ be the phase algorithm. Let $\mu$ be the expected reward function and let $\mu^{*}=\sup_{u\in X}\mu(u)$ be the optimal reward. Let $\Delta(u)=\mu^{*}-\mu(u)$.

By definition of the Lipschitz MAB problem, $\mu$ is a continuous function on the metric space $(L,X)$. Therefore the supremum $\mu^{*}$ is achieved by some strategy (call such strategies optimal). Say that a run of algorithm $\mathcal{A}_{\mathtt{ph}}(T)$ is well-covered if at every time $t\leq T$ some optimal strategy is covered.

Say that a run of algorithm $\mathcal{A}_{\mathtt{ph}}(T)$ is clean if the property in Claim 2.2 holds for all times $t\leq T$. Note that a given run is clean with probability at least $1-T^{-2}$. The following lemma adapts the technique from Lemma 2.5 to the present setting:

Consider a clean run of algorithm $\mathcal{A}_{\mathtt{ph}}(T)$.

If strategies $u,v$ are active at time $t\leq T$ then $\Delta(v)-\Delta(u)\leq 4r_{t}(v)$.