Efficient and Robust High-Dimensional Linear Contextual Bandits

1 Introduction

The contextual bandit is a popular model for sequential decision-making problems [Auer, 2002; Dani et al., 2008; Chu et al., 2011; Abbasi-Yadkori et al., 2011]. In contextual bandit problems, a decision maker repeatedly (a) receives a set of contexts (or actions), (b) chooses an action, and (c) observes a reward for the chosen action. The goal is to maximize the expected cumulative reward over some time horizon. Recently, contextual bandits have been applied to many machine learning tasks, including personalized recommendation [Li et al., 2010], web advertising [Tang et al., 2013], social network analysis [Zhao et al., 2014] and mobile health platforms [Tewari and Murphy, 2017].

Contextual bandits have been widely studied in recent years [Langford and Zhang, 2008; Tang et al., 2013]. The traditional methods for linear contextual bandits including upper-confidence bound algorithms [Chu et al., 2011;

Abbasi-Yadkori et al., 2011] and Thompson sampling algorithms [Agrawal and Goyal, 2013; Russo and Van Roy, 2014]. Some other works extends linear bandits to generalized linear models [Filippi et al., 2010; Li et al., 2017; Dumitrascu et al., 2018]. A famous algorithm for linear contextual bandits is LinUCB [Chu et al., 2011], which regret bound is O(√dT log3 (KT log(T)/δ)). Here d is the dimension of the contextual vectors and T is the time horizon. This result was improved to O(d√T log(T) + √dT log(T) log(1/δ)) [Abbasi-Yadkori et al., 2011], which is irrelevant to the number of arms K.

In the big data era, the dimension of the data grows rapidly. In high-dimensional situation, i.e., d ≈ T, most traditional bandit algorithms are time-consuming. Also, the upper regret bounds become larger with the growth of the dimension. Some recent works focus on high dimensional linear contextual bandits. SLUCB [Carpentier and Munos, 2012] achieves a regret bound O(S√T) by assuming that the contextual data contains only S non-zero components. BallEXP [Deshpande and Montanari, 2012] leverages the technique of ball exploration in the high-dimensional space, but their regret bound is very loose. These two methods are still less efficient in practice because they require O(d2 ) time in each round. Calandriello et al. [2019] proposed an efficient Gaussian process based algorithm for kernel bandits. But their regret bound is ˜O(d√T) for linear kernels.

Recently, some researchers apply matrix sketching techniques to contextual bandit problems [Yu et al., 2017; Kuzborskij et al., 2019]. In [Yu et al., 2017], random projection was adopted to map the high-dimensional contextual information to a random m-dimensional subspace and proposed Contextual Bandits with RAndom Projection (CBRAP) algorithm. Though CBRAP successfully reduces the update time from O(d2 ) to O(md +m3 ), the random projection introduces an additive error εT to their regret bound. To enable the failure probability δ away from 1, the parameter ε has to be Ω(m-1/2 ). Kuzborskij et al. [2019] propose SOFUL algorithm by adopting Frequent Directions (FD) to sketch covariance matrices of linear contextual bandits. Since FD [Liberty, 2013; Ghashami et al., 2016] has good theoretical guarantees in streaming setting, it is more suitable for contextual bandits than random projection. Due to the advantage of FD, SOFUL only require O(md) update time and achieve upper regret bound as ˜O((1+∆T )3/2 (m+d log(1+∆T ))√T ), where ∆T is upper bounded by the spectral tail of the covariance matrix.

However, FD still has some drawbacks when applied to contextual bandits. First, the sequence of covariance matrices satisfies the positive definite monotonicity, i.e. Vt ⪰ Vt-1, where Vt is the covariance matrix in the t-th round. But FD produces a rank-deficient approximation which destroys the positive definite monotonicity of covariance matrices. This deficiency leads to additional terms in the regret bounds of contextual bandits. Specifically, the regret bound of [Kuzborskij et al., 2019] is associated with the spectral tail to the power of 3/2. However, the sketch size is usually much smaller than the rank of covariance matrix in practice. Thus their bounds may be heavily affected by the spectral tail.

In this paper, we present a variant of Frequent Directions, which we call Spectral Compensation Frequent Directions (SCFD). To overcome the disadvantages of FD, SCFD compensates a diagonal matrix which contains spectral information to the result of FD. We further adopt SCFD to accelerate LinUCB, and propose an efficient algorithm for high-dimensional linear contextual bandits, which is called Contextual Bandits via Spectral Compensation Frequent Directions (CBSCFD). Unlike the regularization term used in [Kuzborskij et al., 2019], which is invariant during the sequential decisions, the compensated diagonal matrix of SCFD changes adaptively in each round. Compare with previous methods for contextual bandits, our method provide better regret bounds in highdimensional cases. In addition, our algorithm is much less sensitive to the regularization hyper-parameter, which means that our method is robust.

The main contributions of this paper are summarized as follows:

• We propose SCFD algorithm for matrix sketching. SCFD can approximate a sequence of incremental covariance matrices while keeping the positive definite monotonicity.
• We propose CBSCFD for high-dimensional linear contextual bandits. Our methods only requires O(md) time and O(md) space to update the model in each round. Also, our methods obtain a regret bound of ˜O((√m+d log(1+∆T )+√∆T )√mT), which is better than state-of-the-art methods. Here ∆T is upper bounded by the spectral tail (sum of the last d -m+ 1 singular values) of the covariance matrix.
• We validate our approach on both synthetic and realworld data sets. The result of experiments shows that our algorithm outperforms other state-of-the-art algorithms in the high-dimensional setting.

2 Preliminaries

In this section, we first show notations used in this paper. Then we describe the problem setting of linear contextual bandits. Finally we introduce recent works for Frequent Directions.

2.1 Notation and Definition

Let X denote the context space and A = {1, . . . ,K} denote the action space. Suppose the total rounds of playing bandits is T . We use ˜O notation to hide log(T ) in the complexity analysis. We use Im to denote m×m identity matrix, and 0 to denote a zero vector or matrix of appropriate size. For a vector x ∈ Rd , let ‖x‖2 be the ℓ2-norm of x. For a positive semidefinite (PSD) matrix A, the weighted 2-norm of vector x is defined by ‖x‖A = √x⊤Ax. We denote the inner product as 〈·, ·〉 and the weighted inner product as xA⊤y = 〈x, y〉A. Let det(A) be the determinant of A. For two PSD matrices A and B, we use A ⪰ B to represent the fact that A - B is PSD.

Let ρ be the rank of matrix A. The reduced SVD of A is defined as A = UΣV⊤ = ρ∑ i=1 σiuiv⊤ i , where σi are positive singular values in the descending order. That is, σi(A) is the i-th largest singular value of A. Let κ(A) = σmax(A)/σmin(A) be the condition number of A. Let (A)k = ∑ki=1 σiuiv⊤ i denote the best rank-k approximation of A. Additionally, we let ‖A‖F = √∑i,j A2ij be the Frobenius norm and ‖A‖2 = σmax(A) be the spectral norm. We define the positive definite monotonicity as follows:

Definition 1. For a sequence of positive semi-definite matrices {Ai}Ti=1 , we say {Ai}Ti=1 satisfies positive definite monotonicity if and only if

2.2 Problem Setting

We introduce the problem of linear contextual bandits [Chu et al., 2011; Abbasi-Yadkori et al., 2011]. At each round t, the learner receives contexts xt,a for all a ∈ A. Then, the learner chooses an action at and observes a reward yt ∈ [0, 1]. The reward has the structure yt = x⊤t,at θ∗ + ηt where θ∗ ∈ Rd is a unknown true parameter and ηt is a conditionally R-subGaussian noise. That is

This condition implies that

The cumulative regret in this setting is defined by

where a∗=argmaxa∈Ax⊤t,a θ∗ is the optimal action at round t. The goal of the learner is to minimize the regret RT .

2.3 Frequent Directions

Frequent Directions [Liberty, 2013; Ghashami et al., 2016] is a deterministic matrix sketching method for streaming model. It has been applied to speed up many online learning algorithms including linear bandits [Kuzborskij et al., 2019; Luo et al., 2016; Luo et al., 2019]. For any given matrix XT ∈ RT×d which rows come sequentially, FD aims to generate a matrix ZT ∈ Rm×d such that

Here m ≪ min{d, T} is the sketching size. Suppose the given matrix XT = [x1, x2, . . . , xT ]⊤. At round t, FD inserts x⊤t into the last row of Zt-1 and performs following manipulations:

By using the doubling space technique, FD only need O(md) time to update the model per round (see Section 3.2 of [Ghashami et al., 2016]). Moreover, the approximation matrix is bounded by:

where 0 < k < m.

Some variants of FD have been proposed in recent years. Parameterized Frequent Directions [Desai et al., 2016] specifies the proportion of singular values shrunk in each round; Compensative Frequent Directions [Desai et al., 2016] increases the singular values of the sketching matrix. Both methods may increase the performance empirically, but keep the same error bound as traditional FD algorithm. Robust Frequent Directions[Luo et al., 2019] introduces an adaptive regularizer and improves the approximation error bound by a factor 1/2. Though these variants of FD have different levels of improvement on the FD, they all destroy the positive definite monotonicity of covariance matrices and may increase the regret bound when applied to linear contextual bandits.

3 Main Results

In this section, we first present our SCFD algorithm. Then, we propose CBSCFD algorithm for linear bandits based on SCFD, and analyze the complexity of our approach. Finally we provide theoretical analysis on the regret bounds of our algorithm.

3.1 Spectral Compensation Frequent Direction

Reviewing the procedure of Frequent Directions, we notice that FD subtracts a small term δt from singular values in each round. This manipulation will bring approximation errors and break the positive definite monotonicity. Thus, our idea is to compensate the lost spectral information to the approximation. Specifically, we keep a counter αt to add up the total mass of subtracted values during the Frequent Directions procedure. Then, we compensate the reduced spectrum to the sketched matrix by adding a diagonal matrix αtId. Namely, we use a full rank matrix to approximate the original matrix as follows:

where Xt = [x1, x2, . . . , xt]⊤. We present the procedure of SCFD in Algorithm 1. In Algorithm 1, we show how the

Algorithm 1 SCFD

Input: XT = [x1, . . . , xT ]⊤, m, α0 ≥ 0.

• 1: Z0 = 0m×d
• 2: for t = 1, 2, . . . , T do
• 3: Zt ← [Z⊤t-1 , xt]⊤, αt ←αt-1
• 4: if Zt has 2m rows then
• 5: Compute SVD: [U,Σ,V] ← SVD(Zt).
• 6: δt ← σ2m(Zt), αt ←αt-1 + δt.
• 7: ̂Σ ← √max{Σ2 - δtI, 0}.
• 8: Zt ← ̂ΣV⊤.
• 9: Remove zero value rows in Zt
• 10: end if
• 11: end for

Output: ZT , αT .

doubling space technique [Ghashami et al., 2016] is applied to SCFD. Notice that after performing line 5-9, Zt will have only m-1 rows. Thus, the "if" statement is triggered every m+1 iterations, which indicates that the average time cost of SCFD is O(md). Let ∆t = ∑ti=1 δt, then αt = α0 +∆t. We have the following theorem:

Theorem 1. Assume that SCFD runs with α0=0. Let Z⊤t Zt + αtId be the sketch of X⊤t Xt at round t. Then we have

for all 0 < k < m.

Proof. Since αtId is only added on the output matrix, the sketched matrix Zt still satisfies the property of original FD. The Property 1 and Property 2 of Ghashami et al. [2016] shows that Z⊤t Zt +∆tId ⪰ X⊤t Xt ⪰ Z⊤t Zt. Combining the fact that αt = α0 +∆t = ∆t, we have

Using the fact that ∆t ≤ ‖Xt - (Xt)k‖2F /(m- k) for all 0 < k < m [Ghashami et al., 2016, Theorem 3.1], we get the conclusion of Theorem 1.

Theorem 1 shows that the error of SCFD is bounded by the spectral tail of the data matrix. Actually, SCFD has the same error bound as the original Frequent Directions. However, SCFD has the property that the sequence of approximation matrices {Z⊤t Zt +αtId}Tt=0 satisfies the positive definite monotonicity, which is very important in the regret analysis. We formally present the property as follows:

Property 1. Suppose α0 ≥ 0. When SCFD is running, at each round t, we have

Then, for any unit vector w, we can get

The last step holds because of Eq.(2).

Another property is that the approximation matrices of SCFD is more well-conditioned than FD and even the original matrix, which indicates that SCFD will make the whole algorithm more stable. Let VSCFD = Z⊤t Zt + αtId, VFD = Z⊤t Zt+α0Id and V = X⊤t Xt+α0Id. We have the following property:

Property 2. Suppose α0 ≥ 0. When SCFD is running, at each round t, we have

Remark 1. Theorem 1 and Property 2 show that our method makes the approximation matrices both theoretically guaranteed and well-conditioned. To this sense, the αt selected by Algorithm 1 is optimal. Setting αt to a larger value would lead to breaking Theorem 1. Setting αt to a smaller value would cause worse condition number of the approximation matrices.

3.2 Contextual Bandits via Spectral Compensation Frequent Direction

Our method is a sketched version of LinUCB, which find the solution in a confidence ellipsoid [Abbasi-Yadkori et al., 2011]. Suppose Xt = [x1,a1 , x2,a2 , . . . , xt,at ]⊤ be the sequence of selected arms of a contextual bandit. The regularized covariance matrix is defined as

In each round, LinUCB require O(d2 ) to update the inverse of regularized covariance matrix, which is rather costly when d is large. Thus, we adopt SCFD to approximate Vt in LinUCB by setting α0 = λ. We present CBSCFD in Algorithm 2. Then, we show how CBSCFD efficiently computes the inverse of approximated covariance matrix ̂V-1 t . Let Ht = (ZtZ⊤t + αtI)-1 . By Woodbury Formula, we have ̂V-1 t = (Z⊤t Zt + αtI)-1 = (I - Z⊤t HtZt)/αt. When the "if" statement is triggered, We have Zt = ̂ΣV⊤, thus Ht can easily computed as Ht = ( ̂Σ2 + αtI)-1 . When the "if" statement is not triggered, we can compute Ht as follows:

where p = Ht-1Zt-1xt and k = x⊤t xt - x⊤t Z⊤t-1p + αt.

Algorithm 2 CBSCFD

Input: Sketch size m, parameter λ > 0, β > 0.

• 1: ̂ θ0 = 0, α0 = λ, ̂V0 = α0Id, Z0 = 0m×d.
• 2: for t = 1, 2, . . . , T do
• 3: Observe contexts xt,a.

• 5: Receive reward yt.
• 6: Zt ← [Z⊤t-1 , xt,at ]⊤, αt ←αt-1.
• 7: if Zt has 2m rows then
• 8: Compute SVD: [U,Σ,V] ← SVD(Zt).

9:

10:

δt ← σ2m(Zt), αt ←αt-1 + δt.

̂Σ ← √max{Σ2 - δtI, 0}, Zt ← ̂ΣV⊤.

• 11: Ht ← (̂Σ2 +αtI)-1 .
• 12: else
• 13: Compute Ht as (4).
• 14: end if

• 17: end for

Since the size of Ht is at most 2m, CBSCFD require at most O(md) time to compute Ht. In addition, our method do not need to compute the elements of ̂V-1 t because all operations involving ̂V-1 t are matrix-vector multiplications. Therefore, we only need to consider the matrix-vector multiplications involving Zt, which require only O(md) time. As discussed in Section 3.1, SCFD only needs to compute SVD every m+1 round. Thus, the average time cost per round of CBSCFD is O(md). Since we only need to store Zt and Ht, the space complexity of CBSCFD algorithm is O(md).

3.3 Regret Analysis

Define Yt = [y1, y2, . . . , yt]⊤, then we have ̂ θt = ̂V-1 t XtYt. The upper regret bound of Algorithm 2 is summarized in the following theorem.

Theorem 2. Assume that ‖θ∗‖2 ≤ S, ‖xt,a‖2 ≤ L and ηt is a R-sub-Gaussian noise for t ∈ {1, 2, . . . , T}. If Algorithm 2 runs with β = βT (δ), then with probability 1-δ, the regret of Algorithm 2 is

where

Proof sketch. The first step is to find the confidence ellipsoid where θ∗ lies. Actually, we can obtain that θ∗ lies in the set

with probability 1 - δ. Notice that the line 4 of Algorithm 2 is equivalent to solving the following problem:

where Dt is the decision set that xt,a belongs to. Thus, the action at chosen by Algorithm 2 satisfies x⊤t,at ˜ θt ≥ x∗t ⊤θ∗.

We next consider the regret rt at round t:

Since rt ≤ 2, we have

Then, we have

where the last step follow from the following lemma:

Lemma 1.

3.4 Discussion

Briefly, our bound can be written as

According to Theorem 1, we have

for all 0 < k < m. Thus, ∆T is very small when the covariance matrix is approximately low-rank. Especially, when the rank of covariance matrix is less than m, we have ∆T = 0. In this situation, our regret bound becomes ˜O(m√T). When the covariance matrix is not low-rank, our method significantly reduces the influence of ∆T when compared with SOFUL [Kuzborskij et al., 2019]. Note that the regret bound of SOFUL is

Our method reduces the order of ∆T from 3/2 to 1/2. In addition, our regret bound decouples the dimension d and ∆T , which further reduces the influence of ∆T . Finally, our bound is less sensitive to the parameter λ (which is usually a small number in practice) because the term ∆T/λ is in the logarithmic function. Overall, our method is more effective and robust than SOFUL. We summarize the comparison between our theoretical results and state-of-the-art methods in Table 1. From the table, we can find that our method has the best regret bound in high dimensional case.

4 Experiments

In this section, we empirically verify the efficiency and effectiveness of our CBSCFD algorithm. We conduct experiments on both synthetic data and real-world data sets. The baseline approaches include LinUCB [Abbasi-Yadkori et al., 2011], CBRAP [Yu et al., 2017] and SOFUL [Kuzborskij et al., 2019]. For CBRAP algorithm, we use the Gaussian random matrix as the projection matrix because it has better performance. We conduct all experiments on a Linux server which contains 8 processors and has total memory of 32GB. The code is implemented in Matlab R2017b.

4.1 Synthetic Data

We generated a synthetic data set with 100 arms and 2000 features per context. Specifically, all contexts xt,a ∈ R2000 are drawn independently from multivariate Gaussian distributions xt,a ∼ MVN(1, I2000). The true parameter θ∗ is computed as θ∗ = θ′ /‖θ′ ‖2 where θ′ is drawn from a multivariate Gaussian distribution θ′ ∼ MVN(0, I2000). We set T = 1000 and run the experiments for 20 times. The parameter β of all methods is searched in {10-4 , 10-3 , . . . , 1} and λ is searched in {2×10-4 , 2×10-3 , . . . , 2×104 }. We choose the best values for each approach and report the average results in Figure 1.

In Figure 1, we can find that the running time of LinUCB is much larger than other three methods which use matrix sketching. The CBRAP is a little faster than SOFUL and CBSCFD. The reason is that SOFUL and CBSCFD require to perform SVD decomposition, which is much slower than matrix multiplication though they have the same time complexity. Compare the cumulative regrets in Figure 1, we can find that our CBSCFD outperforms other approaches.

4.2 Online Classification

Then, we perform online classification to evaluate the performance of our methods. We follow the experiments setup of [Kuzborskij et al., 2019]. Specifically, we fit the online classification problem into the contextual bandit setting as follows.

Given a data set with data in K clusters, we first choose one cluster as the target cluster. In each round the environment randomly draws one sample from each class and composes a set of contexts of K samples. The learner chooses one sample from the set and observe the reward corresponding to whether the selected sample belongs to the target cluster. The reward is 1 if the selected sample comes from the target cluster, and is 0 otherwise.

We perform our experiments on two real-world data sets: MNIST [LeCun et al., 1998] and CIFAR10 [Krizhevsky and Hinton, 2009]. We summarize the statistic information of both data sets in Table 2. For MNIST data set, we perform experiments with sketch sizes m = 10. For CIFAR10, we set the sketch sizes m = 20. As previous experiment, the parameter β is searched in {10-4 , 10-3 , . . . , 1} and λ is searched in {2 × 10-4 , 2 × 10-3 , . . . , 2 × 104 }. We run the experiments for 20 times and report the average online mistakes in Figure 2. We find that our CBSCFD algorithm outperforms all other methods on MNIST and CIFAR10 data sets. This result validates the effectiveness of our method.

4.3 Robustness of CBSCFD

Finally, we investigate the robustness of our method. We compare the sensitivity to parameter λ between our method and baseline approaches. Since CBRAP always sets λ = 1, we do not include it as baseline. In this experiment, we fix the parameter β = 0.01 and m = 10. Then we perform experiments on MNIST data set with {2×10-4 , 2×10-3 , . . . , 2× 104 }. We present the result in Figure 3. This figure shows that the performance of CBSCFD only changes slightly when λ is changed. But the performance of other two methods significantly depend on the choice of λ. This result validates our theoretical analysis in Property 2 and shows that our method is robust than others.

4.4 Discussion

It is surprising to see that our method outperforms LinUCB, which adopts no approximations. This happens because our experiments focuses on high dimensional setting, i.e., d ≈ T .

When the iteration round t < d, the matrixXtX⊤t is singular. LinUCB uses a constant regularization and enhances the spectrum by λ. When the regulrization parameter λ is very small, the matrix Vt is ill-conditioned, which makes LinUCB unstable. On the other hand, CBSCFD enhances the spectrum by ∆t +λ, where ∆t is updated in each round and no more than the smallest nonzero singular values of XtX⊤t . Thus, the approximated covariance matrix may have better performance than the original one. Also, the covariance matrix of CBSCFD is more well-conditioned than that of LinUCB, which makes the algorithm more stable and less sensitive to λ.

5 Conclusions

In this paper, we present a variant of FD, which is called SCFD, for matrix sketching. We then propose CBSCFD algorithm for high-dimensional linear contextual bandits based on SCFD. Our method is much more efficient than LinUCB and require less space. Compared with previous methods which use matrix sketching to accelerate linear contextual bandits, our method has better upper regret bound and more robust. Finally, the experiments demonstrated the efficiency, effectiveness and robustness of CBSCFD.

Acknowledgments

Luo Luo was partially supported by Baidu academic collaboration program. The corresponding authors Yong Yu and Weinan Zhang thank the support of NSFC 61702327 and 61772333.