Optimal Exploitation of Clustering and History Information in Multi-armed Bandit

1 Introduction

Many sequential decision problems ranging from clinical trials to online ad placement can be modeled as multi-armed bandit problems (classical bandit) [Li et al., 2010]. At each time step, the algorithm chooses one of several possible actions and observes its reward with the goal of maximizing the cumulative reward over time. A useful extension to classical bandit is the contextual multi-arm bandit problem, where before choosing an arm, the algorithm observes a context vector in each iteration [Langford and Zhang, 2007]. In the conventional formulation of these problems, arms are assumed to be unrelated to each other and no prior knowledge about the arms exist. However, applications can often provide historical observations about arms and also similarity information between them prior to the start of the online exploration phase. In this work, we assume that similarity between the arms is given in the form of a fixed pre-clustering of arms and we design algorithms which exploit the historical information and the clustering information opportunistically. In particular, we seek algorithms which satisfy the following property: if the quality of clustering is good, the algorithm should quickly learn to use this information aggressively during online exploration; however, if the quality of clustering is poor, the algorithm should ignore this information. We note at the outset that it is possible to consider alternative formulations of the bandit problem in the presence of history and clustering information. For instance, one alternative is to use clustering metrics such as Dunn or Dunn-like indices [Liu et al., 2010] to decide if the clustering information should be used during online exploration. However, in general, cluster validation metrics are tightly coupled with specific classes of clustering algorithms (e.g., distance vs. density based clustering); hence, we focus on bandit algorithms which are agnostic to specific clustering metrics and work with any given clustering of the arms. Other alternatives include the design of algorithms for optimal pre-clustering of arms prior to online exploration, as well as incrementally modifying the clustering of the arms during online exploration. These are both valuable refinements to the problem we study but are beyond the scope of the current work. In this paper, we focus on the problem of optimal exploitation of the clustering information given as part of the input. For example, in clinical trials it is often the case that one knows that patients belong to clusters with certain characteristics, in algorithm selection it is known that groups of algorithms behave similarly on given inputs, and in advertisement one often has relevant historical ad placement data available. A real-world motivation for our work is the problem of dosing the drug Warfarin [Sharabiani et al., 2015]. Correctly dosing Warfarin is a significant challenge since it is dependent on the patient's clinical, demographic and genetic information. In the contextual bandit setting, this information can be modeled as the context vector and the bandit arms model the various dosage levels. The dosage levels are further grouped into distinct clusters (15 arms and 3 clusters in our dataset). Historical treatment responses for various dosage levels as well as clustering information derived from medical domain knowledge is available as part this problem instance. Another motivating application is web server selection for latency minimization in content distribution networks (CDNs). A CDN can choose mirrored content from several distributed web servers. The latencies of these servers are correlated and vary widely due to geography and network traffic conditions. This domain can be modeled as the classical bandit problem with the bandit arms representing various web servers, and latency being the negative reward. The web servers are further grouped into clusters based on their historical latencies (700 arms and 5 clusters in our dataset). These problem domains share the characteristics of the availability of historical observations to seed the online phase and grouping of arms into clusters either through domain knowledge or through the use of clustering algorithms.

2 RelatedWork

Both the classical multi-armed bandit and the contextual bandit problems have been studied extensively along with their variants [Lai and Robbins, 1985; Auer et al., 2002; Lin et al., 2018; Maillard and Mannor, 2014; Balakrishnan et al., 2019; Nguyen and Lauw, 2014; Korda et al., 2016; Gentile et al., 2017; Bouneffouf and Rish, 2019; Pandey et al., 2007; Shivaswamy and Joachims, 2012; Noothigattu et al., 2018; Bouneffouf et al., 2017]. The works which are closely related to ours are [Pandey et al., 2007] and [Shivaswamy and Joachims, 2012]. [Pandey et al., 2007; Wang et al., 2018] study the classical bandit problem under the same model of arm clustering as in this work, and [Shivaswamy and Joachims, 2012] studies the classical bandit problem under the same model of historical observations as in this work. In contrast to [Pandey et al., 2007; Wang et al., 2018; Shivaswamy and Joachims, 2012], our work provides 1) algorithms which simultaneously incorporate historical observations and clustering information in the classical bandit setting, 2) regret guarantees under tight and adversarial clustering for this setting, 3) algorithms which simultaneously incorporate historical observations and clustering information in the contextual bandit setting; we also provide regret guarantees for our classical bandit algorithm which uses history; prior to this work, we are not aware of such extensions for the contextual bandit setting, and 4) the META algorithm which effectively hedges between the strategy that uses both clustering and historical observations vs. the strategy which uses only the historical observations and not the clustering information.

3 Problem Setting

In this section, we define two new types of a bandit problems.

3.1 Classical Bandit

The classical bandit problem is defined as exploring the response of K arms within T trials. Playing an arm yields an immediate, independent stochastic reward according to some fixed unknown distribution associated with the arm whose support is in (0, 1). The task is to find the reward-maximizing policy. We adapt this scenario by assuming that the arms are grouped into C clusters with arm k assigned to cluster c(k). Unlike the classical setting, we also wish to incorporate historical observations which may be available for the arms. Specifically, for t ∈ {1, 2, . . . , T}, let rk(t) denote the online reward from arm k at time t. For notational convencience, we set it to 0 if k was not played at time t. 1 Let rh k (t) denote the historical reward for the tth instance of playing arm k in history. Hk is the number of historical instances available for arm k, and H is defined as H := ∑Kk=1 Hk. For each arm, the historical rewards are drawn independently from the same distribution as the online rewards. Let θk denote the expected reward for arm k. The goal is to maximize the expected total reward during T iterations E [∑Tt=1 θk(t) ], where k(t) is the arm played in step t, and the expectation is over the random choices of k(t) made by the algorithm. An equivalent performance measure is the expected total regret, which is the amount of total reward lost by a specific algorithm compared to an oracle which plays the (unknown) optimal arm during each step. The expected total regret is defined as:

1 This is purely for notational convenience, and does not affect the mean rewards computed per arm.

with θ∗ def =maxk θk, ∆k def = θ∗ - θk, and nk(t) denotes the number of times arm k has been played until t.

3.2 Contextual Bandit

The contextual bandit with history and pre-clustered arms is defined as follows: At each step t ∈ {1, ..., T}, the player is presented with a context (feature vector) ⃗xt ∈ Rd before playing an arm from the set A = {1, . . . ,N} that are grouped into C known clusters. Let rk(t) denote the reward which the player can obtain by playing arm k at time t given context ⃗xt. As in [Chu et al., 2011], we will primarily focus on bandits where the expected reward of an arm is linearly dependent on the context. Specifically, ∀k, t : rk(t) ∈ [0, 1] and E[rk(t)|⃗xt] = θ⊤ k ⃗xt where θk ∈ Rd is an unknown coefficient vector associated with the arm k which needs to be learned from data. To incorporate historical information about rewards of the arms in a principled manner, we assume that each arm k is associated with a matrix Hk ∈ Rd×d which records covariance information about the contexts played in history during times t with 1 ≤ t ≤ Hk. Hk is computed using all observed context ⃗xt so that:

Here, Id is the identity matrix of dimension d. The arm is also associated with a vector parameter bhk which is the weighted sum of historical contexts, where the weights are the respective rewards:

The role of the covariance matrix in HLINUCBC is analogous to its role in LINUCB which in turn is analogous to its role in least squares linear regression.

4 HUCBC for Classical Bandit

One solution for the classical bandit problem is the well known Upper Confidence Bound (UCB) algorithm [Auer et al., 2002]. This algorithm plays the current best arm at every time step, where the best arm is defined as one which maximizes the sum of observed mean rewards and an uncertainty term. We adapt UCB for our new setting such that it can incorporate both clustering and historical information. Our algorithm incorporates the historical observations by utilizing it both in the computation of the observed mean rewards and the uncertainty term. Our algorithm incorporates the clustering information by playing at two levels: first picking a cluster using a UCB-like strategy at each time step, and subsequently picking an arm within the cluster, again using a UCB-like strategy.

The pseudocode for HUCBC is presented in Algorithm 1 and the mean reward for arm k is defined in (2).

At each time step t of the exploration, HUCBC computes the quantity HUCBCk(t) for arm k using (3). HUCBCk(t) represents an optimistic estimate of the reward attainable by playing arm k: this estimate incorporates the mean reward observed for the arm so far including the plays of the arm in history and an upper confidence term to account for the possibility of underestimation due to randomness in the rewards. In a similar manner, HUCBC also computes ˆ θhc i (t) and HUCBCci (t) for each cluster i:

Note that ˆ θhc i (t) is the mean reward observed for cluster i including plays of the cluster in history and HUCBCci (t) represents an optimistic estimate of the reward attainable by playing cluster i. The quantities rhc i (t), rc i (t), nci (t), and Hc i in (4) and (5) are the per-cluster analogues of the corresponding quantities defined per-arm. Also note that, while the percluster quantities carry a superscript c as part of their notation, the per-arm quantities do not. At each time step t, HUCBC first picks the cluster which maximizes HUCBCci (t) and then picks the arm within this cluster which maximizes HUCBCk(t).

Algorithm 1 The HUCBC algorithm

At time t, select cluster i that maximizes HUCBCci (t) in (5) and play arm k in cluster i that maximizes HUCBCk(t) in (3)

4.1 Regret Analysis

We upper-bound the expected number of plays of a sub optimal cluster under tight clustering of arms. Let i∗ denote the cluster containing the best arm. Arms are said to be tightly clustered if: 1) for each cluster i, there exists an interval [li, ui] which contains the expected reward of every arm in cluster i, and 2) for i ̸= i∗ , the intervals [li, ui] and [li∗, ui∗] are disjoint. For any cluster i ̸= i∗ , define δi = li∗ - ui.

Theorem 1 (Tight Clustering). The expected regret E[R(T)] at any time horizon T under tight clustering of the arms in HUCBC is at most the following:

All Proofs can be found in the supplemental material 2 .

Intuition Behind Theorem 1

First, the cumulative regret up to time T is logarithmic in T. Second, as the separation between clusters increases resulting in increased ∆k values, the regret decreases. Third and a somewhat subtle aspect of this regret bound is that the number of terms in the summation equals the number of arms in the optimal cluster + the number of sub-optimal clusters. This number is always upper bound by the total number of arms. In fact, the difference between them can be pronounced when the clustering is well balanced - for example, when there are √n clusters with √n arms each, the total number of terms in the summation is 2√n while the total number of arms is n. When the quality of clustering is good, this is exactly the aspect of the regret bound which tilts the scales in favor of HUCBC compared to UCB or HUCB. We now upperbound the expected number of plays of a sub optimal cluster where an adversary is free to cluster the arms in order to elicit the worst case behavior from HUCBC. For ease of analysis, we will analyze a variant of HUCBC which we denote as HUCBC ′ , which plays UCB at the inter-cluster level and plays HUCB at the intra-cluster level.

Theorem 2 (Adversarial Clustering). The expected regret at any time horizon T under any clustering of the arms in HUCBC ′ satisfies the following:

Here, r, s are constants and ℓk and k∗ are defined as in Theorem 1.

Comparing Theorems 1 and 2

Both these theorems share important similarities. First, the regret is O(logT). Second, as the distance between clusters increase, the regret decreases. Third, the number of terms in the summation equals the number of arms in the optimal cluster + the number of sub-optimal clusters. However, there are significant differences. First, the distance between two clusters in Theorem 2 is measured differently: it is now the difference between the mean rewards of the best arms in the clusters. Second and more importantly, the constants involved in the bound of Theorem 2 arise from the results of [Kocsis and Szepesv´ari, 2006] and are significantly bigger than those involved in the bound of Theorem 1. We emphasize that Theorem 2 establishes only an upper bound on the regret: the actual regret for typical instances that arise in practice can be a lot smaller than this upper bound. The proof of this theorem leverages the martingale concentration inequality derived as part of Theorem 1. This is a key part of the drift condition which needs to be satisfied in order for us to use the result of [Kocsis and Szepesv´ari, 2006] for bounding the performance of UCB in non-stationary environments.

2 All proofs are available in the arXiv version, in the following link https://arxiv.org/abs/1906.03979

5 HLINUCBC for Contextual Bandit

A well known solution for the contextual bandit with linear payoffs is LINUCB [Li et al., 2010] where the key idea is to apply online ridge regression to the training data to estimate the coefficients θk. We propose HLINUCBC (Algorithm 2) which extends this idea with both historical and clustering information.

5.1 Clustering Information

HLINUCBC deals with arms that are clustered; it applies online ridge regression at the per-cluster level to obtain an estimate of the coefficients ˆ θc i for each cluster (Line 7), plays the best cluster and then applies online ridge regression to the arms within the chosen cluster to obtain an estimate of the coefficients ˆ θk for each arm (Line 6). To find the best cluster, at each trial t, HLINUCBC computes the quantities:

For each cluster i and selects the cluster with the highest value of pct,i (Line 4). This quantity encapsulates the estimated reward from this cluster, along with an uncertainty term. Then, HLINUCBC finds the best arm within this cluster by computing for each arm k in this cluster, the quantity (9) and selects the arm with the highest value pt,k (Line 5).

5.2 Historical Information

HLINUCBC applies online ridge regression to the historical data at both per-cluster and per-arm levels. The aim is to collect enough information about how the context vectors and rewards relate to each other for each cluster and arm using the historical data, so that it can jump-start the algorithm by achieving a low number of errors at the early stages of the online exploration. At the initialization step, HLINUCBC is seeded with Hci and Hk which are respectively the history matrices for the clusters and arms. This is in contrast to LINUCB, where the initialization is done using an identity matrix. It is also seeded with the vectors bhc i and bhk , which record the weighted sum of historical contexts, with the weight being the rewards. In contrast, in LINUCB, this quantity is initialized to 0.

Algorithm 2 HLINUCBC

Input: α ∈ R>0, history matrices Hci for each i ∈ {1, . . . , C}, Hk for each k ∈ {1, . . . ,K}, weighted sum of contexts bhc i and bhk .

• 1: for arm k ∈ {1, . . . ,K} do Ak ←Hk, bk ← bhk
• 2: for cluster i ∈ {1, . . . ,C} do Aci ←Hci , bci ← bhc i
• 3: for t ∈ {1, . . . , T} do
• 4: Choose cluster i(t) = argmaxi pct,i
• 5: Play arm k(t) = argmaxk|c(k)=i(t) pt,k
• 6: Ak(t) ← Ak(t) + xtx⊤t , bk(t) ← bk(t) + rk(t)(t)xt, ˆ θk(t) ← A-1 k(t) bk(t)
• 7: Aci(t) ← Aci(t) + xtx⊤t , bci(t) ← bci(t) + rk(t)(t)xt, ˆ θc i(t) ← Ac-1 i(t) bi(t)

5.3 Regret Analysis

Theorem 3 shows that the HLINUCB upper bound has log( det(At) det(H) ) under the square root whereas LINUCB has log(det(At). Recall from [Abbasi-Yadkori et al., 2011] that LINUCB has a regret guarantee which is almost the same as the one in Theorem 3 except for the det(H) term.

Theorem 3. With probability 1 - δ, where 0 < δ < 1, the upper bound on the R(T) for the HLINUCB in the contextual bandit problem, K arms and d features (context size) is as follows:

with ||xt||2 ≤ L and φ ∈ R

We demonstrate in the following that det(At) det(H) ≤ det(At) and thereby show that HLINUCB has a provably better guarantee than LINUCB. The matrix H can be written as I + Dh where I is the identity matrix and Dh is the design matrix constructed using the contexts in history. Both I and Dh are real symmetric and hence Hermitian matrices. Further, Dh is positive semi-definite since Dh = ∑i xixTi , where the xi are the historical contexts; to see this, note that ∀y, yT Dhy = ∑i yT xixTi y = ∑i (xTi y)2 ≥ 0. Since all the eigenvalues of I equal 1 and since all the eigenvalues of Dh are non-negative, by Weyl's inequality in matrix theory for perturbation of Hermitian matrices [Thompson and Freede, 1971], the eigenvalues of H are lower-bounded by 1. Hence det(H) which is the product of the eigenvalues of H is lower-bounded by 1 which proves our claim.

6 METAAlgorithm

Intuitively, HUCBC can be expected to outperform HUCB when the quality of clustering is good. However, when the clustering quality is poor, this is far less likely to be the case. In order to choose between these two strategies correctly, we employ the META algorithm. Specifically, for the classical bandit problem, META uses UCB to decide between HUCBC and HUCB at each iteration. For the contextual bandit problem, META uses UCB to decide between HLINUCBC and HLINUCB at each iteration. The basic idea is that if the clustering quality is poor, the fraction of the time when META plays the strategy with both clustering and history will become vanishingly small, leading to the desired behavior.

Theorem 4. The META algorithm is asymptotically optimal for the classical bandit problem under the assumption that the drift conditions of [Kocsis and Szepesv´ari, 2006] hold for HUCBC.

Theorem 4 uses the assumption that HUCBC also satisfies the drift conditions like HUCB. In Theorem 1, we show that HUCB satisfies the drift conditions; this provides some evidence to support the assumption that HUCBC also satisfies them.

7 Experimental Evaluation

In this section, we present the experimental evaluation of our algorithms with synthetic and real world datasets.

7.1 Experiments with Synthetic Classical Bandit

We compare our proposed strategies HUCBC (Section 4) and META (Section 6) to the state-of-the-art competitors UCB [Auer et al., 2002], HUCB [Shivaswamy and Joachims, 2012], and UCBC [Pandey et al., 2007]. HUCB is the degenerate version of HUCBC where all arms belong to the same cluster, i.e., no use of clustering information is made only historical data is employed. In contrast, UCBC is the degenerate version which uses the clustering information but no historical data. Our synthetically generated data assumes 10 clusters and 100 arms. A random permutation assigns each arm k to a cluster c(k), where the centroid of cluster i is defined as λ(i) = 1 2 (ui + 1i ) and ui ∼ U(0, 1). The reward obtained when arm k is played is sampled from U(0, 2αkλ(c(k))), where αk is a arm dependent constant. Thus, the expected reward for cluster i is λ(i). The historical data is generated as follows: for 25% we generate data playing them X times where X is sampled from a Poisson distribution with parameter 10. We report the results of 20 trials in in Figure 1a. Each trial consisted of 104 rounds and we plot the the number of rounds per-round-reward (cumulative reward until that round / number of rounds). The error bars correspond to the interval of ±1 standard deviation around the mean. Clearly, the per-round-reward of HUCBC is the fastest to converge to that of the best arm. Interestingly, while historical data improves the performance of HUCB over UCB only to a small degree (possibly due to asymmetry in history), combining this information with the clustering information improves the performance of HUCBC over UCBC to a significantly larger degree. This is an effect of the fact that even though historical data is sparse and asymmetric at the arm level, combining this information at the cluster level is more impactful. META converges rather quickly to the correct choice (HUCBC) in this setting.

7.2 Experiments with Synthetic Contextual Bandit

We will now compare our proposed contextual bandits HLINUCBC (Section 5) and the META algorithm selection to LINUCB [Li et al., 2010], HLINUCB and LINUCBC. Similarly to HUCB and UCBC, HLINUCB and LINUCBC are degenerated versions of HLINUCBC using either only the historical data or the clustering information.

The synthetic data was created by assuming 10 clusters and 100 arms. Again, a random permutation assigns each arm k to a cluster c(k). The centroid θc i of cluster i is sampled from N(0, I5). The coefficient θk of arm k is defined as θk = θc i + ϵνk, where νk is sampled independently at random from N(0, I5). The reward for playing arm k in context x is sampled from U(0, 2θ⊤ k x). Thus, our synthetically generated problem is linear in the input and the expected distance between clusters is √5ϵ. By varying ϵ, we control the tightness of the clusters and can observe the impact of clustering information with varying quality of clusters. Contexts in each round of a trial are drawn i.i.d from the multivariate normal distribution N(0, I5). We created asymmetric historical data for arms by playing an arm X times with X distinct contexts, where X ∼ P oisson(10).

We report the results for ϵ = 0.1 in Figure 1b. As in the case of classical bandits, we repeat the experiment 20 times, where each trial consists of 10,000 rounds. The error bars correspond to the interval of ±1 standard deviation around the mean. HLINUCBC is clearly outperforming its competitors and META is able to identify HLINUCBC as the stronger method over HLINUCB. In this set up, historical data and clustering are equally important such that HLINUCB and LINUCBC provide similar results. LINUCB clearly provides the worst results. We also compare the performance of HLINUCBC vs. LINUCBC under different values of ϵ ∈ {0.1, 0.8, 3.2}. We normalize the rewards in these three distinct settings to enable a meaningful comparison. We present the results in Figure 1c. Since HLINUCBC utilizes historical data in addition to the clustering information, we can see that it improves upon the performance of LINUCBC for every setting of ϵ.

7.3 Experiments with Real-World Data

We compare our bandit algorithms on two different realworld problems. The classical bandits are compared on the task of web server selection while the contextual bandits are analyzed for the Warfarin drug dosage problem.

Web Server Selection

We evaluate the classical bandits on the problem which is commonly known as the Content Distribution Network. Essentially one needs to decide from what source one should pull content available at multiple sources while minimizing the cumulative latency for successive retrievals. Similar to [Vermorel and Mohri, 2005], we assume that only a single resource can be picked at a time. The university web page data set 3 features more than 700 sources with about 1300 response times each. In order to facilitate our clustering approach in this setting, we perform two types of clustering: 1) split the resources based on average latencies into five categories ranging from 'fast' to 'slow', 2) based on domain names into 17 clusters. Historical data was generated by choosing 200 observations in total at random. In Figures 1d and 1e we show the mean cumulative reward for the UCB, UCB with history (HUCB), UCB with clustering (UCBC), UCB with both (HUCBC), and META over 10 repetitions. Before each experiment, the data has been shuffled. We can observe a clear impact of employing clustering and history and the combination of both, and the type of clustering. The first type of clustering achieves an effective grouping of arms while the second one does not. Confirming our observations on the synthetic data, only clustering information provides better results than only historic data when clustering is of good quality. The two kinds of clustering also highlight the usefulness of our META approach that in both cases converges to the correct approach.

3 https://sourceforge.net/projects/bandit/

Warfarin Drug Dosage

The Warfarin problem data set is concerned with determining the correct initial dosage of the drug Warfarin for a given patient. Correct dosage is variable due to patient's clinical, demographic and genetic context. We select this benchmark because it enables us to compare the different algorithms since this problem allows us to create a hierarchical classification data set. Originally, the data set was converted to a classification data set with three classes using the nominal feedback of the patient. We create a hierarchy as follows. We divide each of the original three classes into five more granular classes. Bandit methods which do not use hierarchy will simply tackle this problem as a classification task with 15 classes. Others will first assign instances to one of the three classes and finally decide to choose one of the final five options. The order of the patients is shuffled, 1500 of them are chosen as historical data. We report the mean and standard deviation of 10 runs in Figure 1f. HLINUCBC is outperforming all competitor methods and also META is able to successfully detect that HLINUCBC is the dominating method. For this problem HLINUCB provides better results than LINUCBC, indicating that historic data is worth more than clustering information.

8 Conclusions

We introduced a variety of algorithms for classical and contextual bandits which incorporate historical observations and pre-clustering information between arms in a principled manner. We demonstrated their effectiveness and robustness both through rigorous regret analysis as well as extensive experiments on synthetic and real world datasets. Two interesting open problems emerge from this work: 1) Are there instance independent regret bounds for HUCBC which depend only on the total number of clusters and the number of arms in the optimal cluster? 2) What are the upper and lower bounds on the regret of HLINUCBC?