Doubly-Robust Lasso Bandit
Gi-Soo Kim Myunghee Cho Paik
stat.ML cs.LG















Doubly-Robust Lasso Bandit
    
  Gi-Soo Kim 

  Department of Statistics

  Seoul National University

  
   

  
   Myunghee Cho Paik 

  Department of Statistics

  Seoul National University

  
   

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

    December 30, 2023
=============================================================================================================================================================================================================================




Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such
as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, d. In many applications however, it is often the case that contexts are high-dimensional with only a sparse subset of size s_0 (≪ d) being correlated with the reward. We consider the stochastic linear contextual bandit problem and propose a novel algorithm, namely the Doubly-Robust Lasso Bandit algorithm, which exploits the sparse structure of the regression parameter as in Lasso, while blending the doubly-robust technique used in missing data literature. The high-probability upper bound of the regret incurred by the proposed algorithm does not depend on the number of arms and scales with log(d) instead of a polynomial function of d. The proposed algorithm shows good performance when contexts of different arms are correlated and requires less tuning parameters than existing methods.    




§ INTRODUCTION


Many sequential decision problems can be framed as the multi-armed bandit (MAB) problem <cit.>, where a learner sequentially pulls arms and receives random rewards that possibly differ by arms. While the reward compensation mechanism is unknown, the learner can adapt his (her) decision to the past reward feedback so as to maximize the sum of rewards. Since the rewards of the unchosen arms remain unobserved, the learner should carefully balance between “exploitation", pulling the best arm based on information accumulated so far, and “exploration", pulling the arm that will assist in future choices, although it does not seem to be the best option at the moment. Application areas include the mobile healthcare system <cit.>, web page ad placement algorithms <cit.>, news article placement algorithms <cit.>, revenue management <cit.>, marketing <cit.>, and recommendation systems <cit.>. 



 Contextual MAB algorithms make use of side information, called context, given in the form of finite-dimensional covariates. For example, in the news article recommendation example, information on the visiting user as well as the articles are given in the form of a context vector. In 2010, the Yahoo! team <cit.> proposed a contextual MAB algorithm which assumes a linear relationship between the context and reward of each arm. This algorithm achieved a 12.5% click lift compared to a context-free MAB algorithm. Many other bandit algorithms have been proposed for linear reward models <cit.>. 
 
 The aforementioned methods require the dimension of the context not be too large. This is because in these algorithms, the cumulative gap between the rewards of the optimal arm and the chosen arm, namely regret, is shown to be proportional to a polynomial function of the dimension of the context, d. In modern applications however, it is often the case that the web or mobile-based contextual variables are high-dimensional. <cit.> applied a dimension reduction method <cit.> to the context variables before applying their bandit algorithm to the Yahoo! news article recommendation log data. 
 
In this paper, we introduce a novel approach to the case where the contextual variables are high-dimensional but only a sparse subset of size s_0 is correlated with the reward. We specifically consider the stochastic linear contextual bandit (LCB) problem, where the N arms are represented by N different contexts b_1(t), ⋯, b_N(t)∈ℝ^d at a specific time t, and the rewards r_1(t),⋯, r_N(t)∈ℝ are controlled by a single linear regression parameter β∈ℝ^d, i.e., r_i(t) has mean b_i(t)^Tβ for i=1,⋯,N. The LCB problem is distinguished from the contextual bandit problem with linear rewards (CBL), where the context b(t)∈ℝ^d does not differ by arms but the the reward of the i-th arm is determined by an arm-specific parameter β_i∈ℝ^d, i.e., r_i(t) has mean b(t)^Tβ_i for i=1,⋯,N.   


When the number of arms is large, the CBL approach is not practical due to large number of parameters. Methods for CBL are also not suited to handle the case where the set of arms changes with time. When we recommend a news article or place an advertisement on the web page, the lists of news articles or advertisements change day by day. In this case, it would not be feasible to assign a different parameter for every new incoming item. Therefore, when the number of arms is large and the set of arms changes with time, LCB approaches including the proposed method can be applied while the CBL approaches cannot.

In supervised learning, Lasso <cit.> is a good tool for estimating the linear regression parameter when the covariates are high-dimensional but only a sparse subset is related to the outcome. However, the fast convergence property of Lasso is guaranteed when data are i.i.d. and when the observed covariates are not highly correlated, the latter referred to as the compatibility condition <cit.>. In the contextual bandit setting, these conditions are often violated because the observations are adapted to the past and the context variables for which the rewards are observed converge to a small region of the whole context distribution as the learner updates its arm selection policy.

In the proposed method,  we resolve the non-compatibility issue by coalescing  the methods from missing data literature. We start from the observation that the 
bandit problem is a missing data problem since the rewards for the arms that are not chosen are not observed, hence, missing.  The difference is that in missing data settings, missingness is controlled by the environment and given to the learner while in bandit settings, the missingness is controlled by the learner.  Since the learner controls the missingness, the missing mechanism, or arm selection  probability is known in bandit settings.  Given this probability, we can construct unbiased estimates of the rewards for the  arms  not chosen, using the doubly-robust technique <cit.>, which allows  capitalizing on the context information corresponding to the arms that are not chosen.  These data are observed and available, however, were not utilized by most of the existing contextual bandit algorithms.

We propose the Doubly-Robust Lasso Bandit algorithm which hinges on the sparse structure as in Lasso <cit.>, but utilizes contexts for unchosen arms by blending the doubly-robust technique <cit.> used in missing data literature. The high-probability upper bound of the regret incurred by the proposed algorithm has order O(s_0log(dT)√(T)) where T is the total number of time steps. We note that the regret does not depend on the number of arms, N, and scales with log(d) instead of a polynomial function of d. Therefore, the regret of the proposed algorithm is sublinear in T even when N≫ T and d scales with T. 

<cit.>, <cit.> and <cit.> considered the sparse LCB problem as well. 
  While the high-probability regret bound of <cit.> does not depend on N, it is proportional to √(d) instead of logd, so is not sublinear in T when d scales with T.  <cit.> used an explicit exploration phase to identify the support of the regression parameter using techniques from compressed sensing. Their regret bound is tight scaling with logd, but the algorithm is specific to the case where the set of arms is the unit ball for the ||·||_2 norm and fixed over time. <cit.> leveraged ideas from linear Thompson Sampling and Relevance Vector Machines <cit.>. The theoretical results of <cit.> are weak since they derived the regret bound under the assumption that a sufficiently small superset of the support for the regression parameter is known in advance.  


<cit.> addressed the CBL problem with high-dimensional contexts. They proposed the Lasso Bandit algorithm which uses Lasso to estimate the parameter of each arm separately. To solve non-compatibility, <cit.> used forced-sampling of each arm at predefined time points and maintained two estimators for each arm, one based on the forced-samples and the other based on all samples. They derived a regret bound of order O(Ns_0^2[logT+logd]^2).

For the same problem, <cit.> proposed the Minimax Concave Penalized (MCP) Bandit algorithm which uses forced-sampling along with the MCP estimator <cit.> and improved the bound of <cit.> to O(Ns_0^2[s_0+logd]logT). 

The regrets of  <cit.> and <cit.> increase linearly with N due to separate estimation for each arm. When the number of arms N is bigger than T,  these algorithms should terminate before the forced-sampling of each arm is completed, thus may not be practical. In contrast, the proposed method allows to share information across arms so its performance does not depend on N. In cases where all three methods are applicable, the proposed algorithm requires one less tuning parameter than Lasso Bandit and MCP Bandit, which is a significant advantage for an online learning algorithm as it is difficult to  simultaneously tune the hyperparameters and achieve high reward. 

  
  
  
We summarize the main contributions of the paper as follows.

    
  * We propose a new linear contextual MAB algorithm for high-dimensional, sparse reward models. The proposed method is simple and requires less tuning parameters than previous works.
    
  * We propose a new estimator for the regression parameter in the reward model which uses Lasso with the context information of all arms through the doubly-robust technique.
    
  * We prove that the high-probability regret upper bound of the proposed algorithm is O(s_0log(dT)√(T)), which does not depend on N and scales with logd.
    
  * We present experimental results that show the superiority of our method especially when N is big and the contexts of different arms are correlated.




 §.§ Related Work


The fast convergence of Lasso for linear regression parameter was extenstively studied in <cit.>, <cit.>, and <cit.>. The doubly-robust technique was originally introduced in <cit.> and extensively analyzed in <cit.> under supervised learning setup. <cit.>, <cit.>, and <cit.> are recent works that incorporate the doubly-robust methodology into reinforcement learning but under offline learning settings. <cit.> was the first to blend the doubly-robust technique in the online bandit problem. Their work, which focused on low-dimensional settings, proposed to use the doubly-robust technique as a way of balancing the data over the whole context space which makes the online regression less prone to bias when the reward model is misspecified. 



§ SETTINGS AND ASSUMPTIONS


In the MAB setting, the learner is repeatedly faced with N alternative arms where at time t, the i-th arm (i=1,⋯,N) yields a random reward r_i(t) with unknown mean θ_i(t). We assume that there is a finite-dimensional context vector b_i(t)∈ℝ^d associated with each arm i at time t and that the mean of r_i(t) depends on b_i(t), i.e., θ_i(t)=θ_t(b_i(t)),
where θ_t(·) is an arbitrary function. 
Among the N arms, the learner pulls one arm a(t), and observes reward r_a(t)(t). The optimal arm at time t is a^*(t):=1≤ i ≤ Nargmax{θ_t(b_i(t))}. Let regret(t) be the difference between the expected reward of the optimal arm and the expected reward of the arm chosen by the learner at time t, i.e., 

    regret(t)   =𝔼(r_a^*(t)(t)-r_a(t)(t) | {b_i(t)}_i=1^N, a(t) )
       =θ_t(b_a^*(t)(t))-θ_t(b_a(t)(t)).

Then, the goal of the learner is to minimize the sum of regrets over T steps,
R(T):=∑_t=1^Tregret(t).

We specifically consider a sparse LCB problem, where θ_t(b_i(t)) is linear in b_i(t), 

    θ_t(b_i(t))=b_i(t)^Tβ,   i=1,⋯,N,

where β∈ℝ^d is unknown and ||β||_0=s_0(≪ d), ||·||_p denoting the L_p-norm. Hence, only s_0 elements in β are assumed to be nonzero. We also make the following assumptions, from <ref> to <ref>.
Bounded norms.
Without loss of generality, ||b_i(t)||_2≤ 1,  ||β||_2≤ 1. 


IID Context Assumption.  The distribution of context variables is i.i.d. over time t:

    {b_1(t), ⋯, b_N(t)}i.i.d.∼𝒫_b,

where 𝒫_b is some distribution over ℝ^N× d.

We note in  <ref> that given time t, the contexts from different arms are allowed to be correlated.
 Compatibility Assumption <cit.>.  Let I be a set of indices and ϕ be a positive constant. Define 
    C(I,ϕ)={M∈ℝ^d× d: ∀ v ∈ℝ^d  such that  ||v_I^C||_1≤ 3||v_I||_1, ||v_I||_1^2≤ |I|(v^TMv)/ϕ^2}.

Then ∃ϕ_1>0 such that 
    Σ:=𝔼[b̅(t)b̅(t)^T]∈ C(supp(β), ϕ_1),

where b̅(t)=1/N∑_i=1^Nb_i(t), and supp(β) denotes the support of β.

 <ref> ensures that the Lasso estimate of β converges to the true parameter in a fast rate. This assumption is weaker than the restricted eigenvalue assumption <cit.>. 
Sub-Gaussian error.
The error η_i(t):=r_i(t)-b_i(t)^Tβ is R-sub-Gaussian for some 0<R<O(√(logT/T)), i.e., for every λ∈ℝ, 

    𝔼[exp(λη_i(t))]≤exp(λ^2R^2/2).


Assumption <ref> is satisfied whenever r_i(t)∈ [b_i(t)^Tβ-R,b_i(t)^Tβ+R]. 




§ DOUBLY-ROBUST LASSO BANDIT


Lemma 11.2 of <cit.> shows that when the covariates satisfy the compatibility condition and the noise is i.i.d. Gaussian, the Lasso estimator of the linear regression parameter converges to the true parameter in a fast rate. We restate the lemma. 
<cit.> Let x_τ∈ℝ^d and y_τ∈ℝ be random variables with y_τ=x_τ^Tβ+ε_τ, τ=1,2,⋯,t, where β∈ℝ^d, ||β||_0=s_0, and ε_τ's are i.i.d. Gaussian with mean zero and variance R^2. Let β̂(t) be the Lasso estimator of β based on the first t observations using λ_t=R√(2log(ed/δ)/t) for the regularization parameter in the L_1 penalty, i.e.,

    β̂(t)=βargmin{1/t∑_τ=1^t(y_τ-x_τ^Tβ)^2+λ_t||β||_1}.

If Σ̂_t:=1/t∑_τ=1^t x_τx_τ^T∈ C(supp(β),ϕ) for some ϕ>0, then for ∀δ∈ (0,1), with probability at least (1-δ), 

    ||β̂(t)-β||_1≤4λ_t s_0/ϕ^2=4s_0R/ϕ^2√(2log(ed/δ)/t).



Two hurdles that arise when incorporating Lemma <ref> into the contextual MAB setting are that (a) (non-i.i.d.) the errors ε_τ's are not i.i.d., and (b) (non-compatibility) the Gram matrix Σ̂_t does not satisfy the compatibility condition even under assumption <ref> because the context variables of which the rewards are observed do not evenly represent the whole distribution of the context variables. In the LCB setting, x_τ corresponds to b_a(τ)(τ). Since the learner tends to choose the contexts that yield maximum reward as time elapses, the chosen context variables b_a(τ)(τ)'s converge to a small region of the whole context space. We discuss on remedies to (a) and (b) in Section <ref> and Section <ref>, respectively.   



 §.§ Lasso Oracle Inequality with non-i.i.d. noise


As a remedy to the non-i.i.d. problem, <cit.> proposed a variation of Lemma <ref> which shows that (<ref>) holds when {ε_τ}_τ=1^t is a martingale difference sequence. We restate the proposition of <cit.>.
<cit.> Let ℱ_τ-1 denote the filtration up to time τ-1 in the bandit setting, 
    ℱ_τ-1={x_1,y_1,⋯,x_τ-1,y_τ-1,x_τ},   τ=1,2,⋯,t.
 Suppose the conditions of Lemma <ref> hold except that ε_τ's are i.i.d. Suppose instead that ε_τ|ℱ_τ-1 is R-sub-Gaussian for τ=1,⋯,t. Then for ∀δ∈ (0,1), with probability at least (1-δ), 

    ||β̂(t)-β||_1≤4λ_t s_0/ϕ^2=4s_0R/ϕ^2√(2log(ed/δ)/t).





 §.§ Doubly-robust pseudo-reward


To overcome the non-compatibility problem, in the CBL setting, <cit.> proposed to impose forced-sampling of each arm at predefined O(logT) time steps, which produces i.i.d. data. The following lemma shows that when x_τ's are i.i.d. and 𝔼(x_τx_τ^T)∈ C(supp(β),ϕ), then Σ̂_t∈ C(supp(β),ϕ/√(2)) with high probability.
<cit.>
Let x_1, x_2, ⋯, x_t be i.i.d. random vectors in ℝ^d with ||x_τ||_∞≤ 1 for all τ. Let Σ=𝔼[x_τx_τ^T] and Σ̂_t=1/t∑_τ=1^tx_τx_τ^T. Suppose that Σ∈ C(supp(β),ϕ). Then if t≥3/c^2logd,

    ℙ[Σ̂_t∈ C(supp(β),ϕ/√(2))]≥ 1-exp(-c^2t),

where c=min(0.5, ϕ^2/256s_0).

We derive the following corollary simply by setting the right-hand side of (<ref>) larger than 1-δ'/t^2 . 
 Suppose that the conditions of Lemma <ref> are satisfied. Let z_T=max(3/c^2logd, 1/c^2logT^2/δ') for some δ'∈ (0,1). Then with probability at least 1-δ',  
    Σ̂_t∈ C(supp(β),ϕ/√(2))   for all  t≥ z_T.
 

The setting of <cit.> is different from ours in that they assume the context variable is the same for all arms but the regression parameter differs by arms. <cit.> maintained two sets of estimators for each arm, the estimator based on the forced-samples and the one based on all samples. Whereas the latter is not based on i.i.d. data, using the forced-sample estimator as a pre-processing step of selecting a subset of arms and then using the all-sample estimator to select the best arm among this subset guarantees that there are O(T) i.i.d. samples for each arm, so the all-sample estimator converges in a fast rate as well. 



We propose a different approach to resolve non-compatibility, which is based on the doubly-robust technique in missing data literature. We define the filtration ℱ_t-1 as the union of the observations until time t-1 and the contexts given at time t, i.e.,  
    ℱ_t-1={{b_i(1)}_i=1^N, a(1), r_a(1)(1),⋯,{b_i(t-1)}_i=1^N, a(t-1), r_a(t-1)(t-1),{b_i(t)}_i=1^N}.
 Given ℱ_t-1, we pull the arm a(t) randomly according to probability π(t)=[π_1(t),⋯,π_N(t)], where π_i(t)=ℙ[a(t)=i|ℱ_t-1] is the probability of pulling the i-th arm at time t given ℱ_t-1. We specify the values of π(t) later in Section <ref>. Let β̂(t-1) be the β estimate given ℱ_t-1. After the reward r_a(t)(t) is observed, we construct a doubly-robust pseudo-reward:

    r̂(t)=b̅(t)^Tβ̂(t-1)+1/Nr_a(t)(t)-b_a(t)(t)^Tβ̂(t-1)/π_a(t)(t).
 
Whether or not β̂(t-1) is a valid estimate, this value has conditional expectation b̅(t)^Tβ given that π_i(t)>0 for all i:

    𝔼[r̂(t)|ℱ_t-1]   =𝔼[1/N∑_i=1^N(1-I(a(t)=i)/π_i(t))b_i(t)^Tβ̂(t-1)+1/N∑_i=1^NI(a(t)=i)/π_i(t)r_i(t)|ℱ_t-1]
       =𝔼[1/N∑_i=1^Nr_i(t)|ℱ_t-1]=b̅(t)^Tβ.

Thus by weighting the observed reward r_a(t)(t) with the inverse of its observation probability π_a(t)(t), we obtain an unbiased estimate of the reward corresponding to the average context b̅(t) instead of b_a(t)(t). Applying Lasso regression to the pair (b̅(t),r̂(t)) instead of (b_a(t)(t), r_a(t)(t)), we can make use of the i.i.d. assumption <ref> and the compatibility assumption  <ref> with Corollary <ref> to achieve a fast convergence rate for β as in (<ref>). We later show that when x_τ in Corollary <ref> corresponds to b̅(τ), (<ref>) holds with z_T=O(s_0^2log(dT)).

Since the allocation probability π_a(t)(t) is known given ℱ_t-1, the simple inverse probability weighting (IPW) estimator r̆(t):=r_a(t)(t)/Nπ_a(t)(t) also gives an unbiased estimate for the reward corresponding to the average context. We however show in the next paragraphs that the doubly-robust estimator has constant variance under minor condition on the weight π_a(t)(t) while the IPW estimator has variance that increases with t under the same condition. Constant variance is crucial for the performance of the algorithm, since it affects the convergence property of β̂(t) in (<ref>) and eventually the regret upper bound in Theorem <ref>. We can make the IPW estimator have constant variance as well under stronger condition on π_a(t)(t), but this stronger condition is shown to result in regret linear in T.

Let R̃^2 be the variance of r̂(t) given ℱ_t-1. We have,

    R̃^2   :=Var[r̂(t)|ℱ_t-1]=𝔼[{r̂(t)-b̅(t)^Tβ}^2|ℱ_t-1]
       =𝔼[{b̅(t)^T(β̂(t-1)-β)+η_a(t)(t)/Nπ_a(t)(t)+b_a(t)(t)^T(β-β̂(t-1))/Nπ_a(t)(t)}^2|ℱ_t-1].

Suppose β̂(t-1) satisfies the Lasso convergence property (<ref>), i.e., ||β̂(t-1)-β||_1≤ O(√((logd+log
t)/t)) for t > z_T.   Then we can bound the first and third terms of (<ref>) by a constant under the following restriction,  


    π_a(t)(t)=1/N    for all t≤ z_T
     O(1/N√((logd+logt)/t))     for all t>z_T.
 

Due to assumption <ref> on the sub-Gaussian error η, the second term of (<ref>) is also bounded by a constant under (<ref>). Hence, we have R̃^2 ≤ O(1). Therefore if  (<ref>) holds and if β̂(z_T), β̂(z_T+1), ⋯, β̂(t-1) all satisfy the Lasso convergence property (<ref>), then the pseudo-rewards r̂(1),⋯,r̂(t) all have constant variance. Consequently, the estimate β̂(t) based on {b̅(τ),r̂(τ)}_τ=1^t satisfies (<ref>). Meanwhile, the restriction (<ref>) leads to suboptimal choice of arms at each t with probability that decreases with time. In Theorem <ref>, we prove that the regret due to this suboptimal choice is sublinear in T. 

The variance of r̆(t) given filtration ℱ_t-1 is 𝔼[{η_a(t)(t)/Nπ_a(t)(t)+b_a(t)(t)^Tβ/Nπ_a(t)(t)-b̅(t)^Tβ}^2|ℱ_t-1].

 

As opposed to the first and third terms in (<ref>), the term b_a(t)(t)^Tβ/Nπ_a(t)(t) still increases with t under (<ref>). To achieve a constant variance, we need π_a(t)(t) be larger than a predetermined constant value, 1/Np_min. Simply replacing π_a(t)(t) in r̆(t) with the truncated value π̆_a(t)(t)=max{1/Np_min, π_a(t)(t)} will produce a biased estimate of b̅(t)^Tβ when π_a(t)(t) is actually smaller than 1/Np_min, and the resulting estimate β̂(t) will not satisfy convergence property (<ref>). If we instead directly constrain π_a(t)(t) to be larger than 1/Np_min, this will lead to suboptimal choice of arms at each t with constant probability so the regret will increase linearly in T.  





 §.§ Doubly-Robust Lasso Bandit algorithm


To make π_a(t)(t)=1/N for all t≤ z_T, we simply pull arms according to the uniform distribution when t≤ z_T. Then to ensure π_a(t)(t)≥ O(1/N√((logd+logt)/t)) for all t>z_T,  we randomize the arm selection at each step between uniform random selection 
and deterministic selection using the β estimate of the last step, β̂(t-1). This can be implemented  in two stages. First, sample m_t from a Bernouilli distribution with mean λ_1t=λ_1√((logt+logd)/t), where λ_1>0 is a tuning parameter. Then if m_t=1, pull the arm a(t)=i with probability 1/N, otherwise, pull the arm a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)}. Under this procedure, we have π_a(t)(t)=λ_1t/N+(1-λ_1t)I{a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)}}, which satisfies (<ref>). In practice, we treat z_T as a tuning parameter.

The proposed Doubly-Robust (DR) Lasso Bandit algorithm is presented in Algorithm <ref>. The algorithm selects a(t) via two stages, computes π_a(t)(t), constructs the pseudo-reward r̂(t) and average context b̅(t), and updates the β estimate using Lasso regression on the pairs (b̅(t),r̂(t))'s. Recall that the regularization parameter should be set as λ_2t=O(√(log(d/δ)/t)) to guarantee (<ref>) for a fixed t. To guarantee (<ref>) for every t>z_T, we impute δ/t^2 instead of δ. Hence at time t, we update λ_2t=λ_2√((logt+logd)/t) where λ_2>0 is a tuning parameter. The algorithm requires three tuning parameters in total, while <cit.> and <cit.> require four.





§ REGRET ANALYSIS


Under (<ref>), the regret at time t is regret(t)=b_a^*(t)(t)^Tβ-b_a(t)(t)^Tβ,
where a^*(t)=1≤ i ≤ Nargmax{b_i(t)^Tβ}.
We establish the high-probability regret upper bound for Algorithm <ref> in the following theorem.

 Suppose (<ref>) and assumptions <ref>, <ref>, <ref>, and <ref> hold. Then we have for ∀δ∈ (0,1/2) and ∀δ'∈ (0,δ), with probability at least 1-2δ, 
    R(T)   ≤max(3/C(ϕ_1)^2logd, 1/C(ϕ_1)^2log(T^2/δ'))+√(128)/ϕ_1^2s_0R̃√(T)log(edT^2/δ-δ')+λ_1√(T)log(dT)
       +√(T/2log(1/δ))
       =O(s_0√(T)log(dT)),

where C(ϕ_1)=min(0.5, ϕ_1^2/256s_0) and R̃=O(1).


We provide a sketch of proof in the next section. A complete proof is presented in the Supplementary Material.



 §.§ Sketch of proof for Theorem <ref>


In the DR Lasso Bandit algorithm, each of the T decision steps corresponds to one of the following three groups.

    
  * t≤ z_T: the arms are pulled according to the uniform distribution.
    
  * t>z_T and m_t=1: the arms are pulled according to the uniform distribution.
    
  * t>z_T and m_t=0: the arm a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)} is pulled.

We let z_T=max(3/C(ϕ_1)^2logd, 1/C(ϕ_1)^2log(T^2/δ')). The strategy of the proof is to bound the regrets from each separate group and sum the results. 

Due to assumption <ref> on the norms of b_i(t) and β, regret(t) is not larger than 1 in any case. Therefore, the sum of regrets from group (a) is at most z_T, which corresponds to the first term in Theorem <ref>. We now denote the sum of regrets from group (b) and group (c) as R(T,b) and R(T,c), respectively. We first bound R(T,b) in Lemma <ref>, which follows from the fact that m_t is a Bernouilli variable with mean λ_1t and  Hoeffding's inequality.  

 With probability at least 1-δ,

    R(T,b)≤∑_t=z_T^Tλ_1t+√(Tlog(1/δ)/2)≤λ_1√(T)√(log(dT))√(1+logT)+ √(Tlog(1/δ)/2).


To bound R(T,c), we further decompose group (c) into the following two subgroups, where we set d_t=√(128)/ϕ_1^2s_0R̃√(log(edt^2/(δ-δ'))/t) with R̃=O(1).

(c-a) t>z_T, m_t=0 : a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)} is pulled and ||β̂(t-1)-β||_1≤ d_t-1.

(c-b) t>z_T, m_t=0 : a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)} is pulled and ||β̂(t-1)-β||_1>d_t-1.

We first show in Lemma <ref> that the subgroup (c-b) is empty with high probability. Since β̂(t) is computed from the pairs {b̅(τ), r̂(τ)}_τ=1^t where the average contexts b̅(τ)'s satisfy the compatibility condition (<ref>) and the pseudo-rewards r̂(τ)'s are unbiased with constant variance, Lemma <ref> can be applied on β̂(t). 

Suppose (<ref>) and assumptions <ref>, <ref>, <ref>, and <ref> hold. Let d_t=√(128)/ϕ_1^2s_0R̃√(log(edt^2/(δ-δ'))/t). Then we have for ∀δ∈ (0,1), for every t≥ z_T, 

    ℙ(||β̂(t)-β||_1 > d_t |  ||β̂(t-1)-β||_1 < d_t-1, ⋯, ||β̂(z_T)-β||_1 < d_z_T)≤δ/t^2.

Hence, with probability at least 1-δ,

    ||β̂(t)-β||_1<d_t  for every t≥ z_T.


Finally when t belongs to group (c-a), regret(t) is trivially bounded by d_t. Hence we can bound R(T,c) as in the following lemma.
With probability at least 1-δ,

    R(T,c)≤∑_t=z_T^Td_t≤√(128)/ϕ_1^2s_0R̃√(T)log(edT^2/δ-δ').






§ SIMULATION STUDY






We conduct simulation studies to evaluate the proposed DR Lasso Bandit and the Lasso bandit  <cit.>. We set N=10, 20, 50, or 100, d=100, and s_0=5. For fixed j=1,⋯,d, we generate [b_1j(t),⋯,b_Nj(t)]^T from 𝒩(0_N,V) where V(i,i)=1 for every i and V(i,k)=ρ^2 for every i ≠ k. We experiment two cases for ρ^2, either ρ^2=0.3 (weak correlation) or ρ^2=0.7 (strong correlation). We generate  η_i(t)i.i.d.∼𝒩(0,0.05^2) and the rewards from (<ref>). We set ||β||_0=s_0 and generate the s_0 non-zero elements from a uniform distribution on [0,1]. 

We conduct 10 replications for each case. The Lasso Bandit algorithm can be applied in our setting by considering a Nd-dimensional context vector b(t)=[b_1(t)^T,⋯,b_N(t)^T]^T  and a Nd-dimensional regression parameter β_i for each arm i where β_i=[I(i=1)β^T,⋯,I(i=N)β^T]^T. For each algorithm, we consider some candidates for the tuning parameters and report the best results. For DR Lasso Bandit, we advise to truncate the value r̂(t)  so that it does not explode.








Figure <ref> shows the cumulative regret R(t) according to time t. When the number of arms N is as small as 10, Lasso Bandit converges faster to the optimal decision rule than DR Lasso Bandit. However, we notice that the regret of Lasso Bandit in the early stage is larger than DR Lasso Bandit, which is due to forced-sampling of arms. With larger number of arms, DR Lasso Bandit outperforms Lasso Bandit. Compared to Lasso Bandit, the regret of DR Lasso Bandit decreases dramatically as the correlation among the contexts of different arms increases. We also verify that the performance of the proposed method is not sensitive to N, while the regret of Lasso Bandit increases with N.   




§ CONCLUDING REMARKS


Sequential decision problems involving web or mobile-based data call for contextual MAB methods that can handle high-dimensional covariates. In this paper, we propose a novel algorithm which enjoys the convergence properties of the Lasso estimator for i.i.d. data via a doubly-robust technique established in the missing data literature. The proposed algorithm attains a tight high-probability regret upper bound which depends on a polylogarithmic function of the dimension and does not depend on the number of arms, overcoming weaknesses of the existing algorithms. 



[Abbasi-Yadkori et al., 2011]Abbasi-YadkoriAbbasi-Yadkori, Y., Pál, D. and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312–2320, 2011.
[Abbasi-Yadkori et al., 2012]Abbasi-Yadkori12Abbasi-Yadkori, Y., Pál, D. and Szepesvari, C. Online-to-confidence-set conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1–9, 2012.
[Agrawal and Goyal, 2013]AgrawalAgrawal, S. and Goyal, N. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th  International Conference on Machine Learning, pp. 127–135, 2013.
[Auer, 2002]AuerAuer, P. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3:397–422, 2002.
[Bang and Robins, 2005]BangBang, H. and Robins, J.M. Doubly robust estimation in missing data and causal inference models. Biometrics, 61(4):962-973, 2005.
[Bastani and Bayati, 2015]BastaniBastani, H. and Bayati, M. Online decision-making with high-dimensional covariates. Available at SSRN 2661896, 2015.
[Bickel et al., 2009]BickelBickel, P., Ritov, Y. and Tsybakov, A. Simultaneous analysis of Lasso and Dantzig selector. Annals of Statistics, 37:1705–-1732, 2009.
[Carpentier and Munos, 2012]CarpentierCarpentier, A. and Munos, R. Bandit theory meets compressed sensing
for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics (AISTATS), pp. 190–198, 2012. 
[Chu et al., 2009]Chu09Chu, W., Park, S.T., Beaupre, T., Motgi, N., Phadke, A., Chakraborty, S. and Zachariah, J. A case study of behavior-driven conjoint analysis on Yahoo!: front page today module. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1097-1104, 2009.
[Chu et al., 2011]Chu11Chu, W., Li, L., Reyzin, L. and Schapire, R.E. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 208–214, 2011.
[Dani et al., 2008]Dani Dani, V., Hayes, T. P. and Kakade, S. M. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, pp. 355–-366, 2008.
[Dimakopoulou et al., 2018]DimakopoulouDimakopoulou, M., Zhou, Z., Athey, S. and Imbens, G. Balanced Linear Contextual Bandits. arXiv preprint arXiv:1812.06227, 2018.
[Dudík et al., 2014]DudikDudík, M., Erhan, D., Langford, J. and Li, L. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-511, 2014.
[Farajtabar et al., 2018]FarajtabarFarajtabar, M., Chow, Y. and Ghavamzadeh, M. More Robust Doubly Robust Off-policy Evaluation. In Proceedings of the 35th International Conference on Machine Learning, pp. 1446-1455, 2018.
[Ferreira et al., 2018]Ferreira Ferreira, K., Simchi-Levi, D. and Wang, H. Online network revenue management using Thompson sampling. Operations Research, 66(6):1586–1602, 2018.

[Gilton and Willett, 2017]GiltonGilton, D. and Willett, R. Sparse linear contextual bandits
via relevance vector machines. In International Conference on Sampling Theory and Applications (SampTA), pp. 518–522, 2017.
[Jiang and Li, 2016]JiangJiang, N. and Li, L. Doubly Robust Off-policy Value Evaluation for Reinforcement Learning. In Proceedings of the 33rd International Conference on Machine Learning, pp. 652-661, 2016.
[Kawale et al., 2015]Kawale Kawale, J., Bui, H.H., Kveton, B., Tran-Thanh, L. and Chawla, S. Efficient Thompson sampling for online matrix-factorization recommendation. In Advances in Neural Information Processing Systems, pp. 1297–1305, 2015.
[Lai and Robbins, 1985]Lai85 Lai, T.L. and Robbins, H.  Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, 1985.
[Langford et al., 2008]Langford Langford, J., Strehl, A. and Wortman, J. Exploration scavenging. In Proceedings of the 25th International Conference on Machine Learning, pp. 528–535, 2008.
[Li et al., 2010]Li10 Li, L., Chu, W., Langford, J. and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World wide web, pp. 661–670, 2010.

[Robbins, 1952]Robbins Robbins, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527–535, 1952. 
[Robins et al., 1994]RobinsRobins, J. M., Rotnitzky, A. and Zhao, L. P. Estimation of regression coefficients when some regressors are not always observed. Journal of the American statistical Association, 89(427):846-866, 1994.
[Schwartz et al., 2017]Schwartz Schwartz, E.M., Bradlow, E.T. and Fader, P.S. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500–522, 2017. 
[Tewari and Murphy, 2017]Tewari and Murphy Tewari, A., and Murphy, S.A. From ads to interventions: contextual bandits in mobile health. In Mobile Health (pp. 495–517). Springer, Cham, 2017.
[Tibshirani, 1996]TibshiraniTibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[Tipping, 2001]TippingTipping, M. E. Sparse Bayesian learning and the relevance vector machine. Journal of machine learning research, 1(Jun):211-244, 2001.
[van de Geer, 2007]VanDeGeer07van de Geer, S. The deterministic Lasso. In JSM proceedings, American Statistical Association, (see also
http://stat.ethz.ch/research/research reports/2007/140),  2007.
[van de Geer and Bühlmann, 2009]VanDeGeervan de Geer, S. A. and Bühlmann, P. On the conditions used to prove oracle results for the Lasso. Electronic Journal of Statistics, 3:1360–1392, 2009.
[Wang et al., 2018]WangWang, X., Wei, M. M. and Yao, T. Minimax Concave Penalized Multi-Armed Bandit Model with High-Dimensional Convariates. In Proceedings of the 35th International Conference on Machine Learning, pp. 5187–5195, 2018.
[Yahoo, 2019]Yahoo Yahoo! Webscope. Yahoo! Front Page Today Module User Click Log Dataset, version 1.0. <http://webscope.sandbox.yahoo.com>. Accessed: 09/01/2019.
[Zhang, 2010]ZhangZhang, C. H. Nearly unbiased variable selection under minimax concave penalty. Annals of statistics, 38(2):894-942, 2010.







Supplementary Material: 
 Doubly-Robust Lasso Bandit 
    
  Gi-Soo Kim 

  Department of Statistics

  Seoul National University

  
   

  
   Myunghee Cho Paik 

  Department of Statistics

  Seoul National University

  
   

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

    December 30, 2023
=============================================================================================================================================================================================================================








§ PROOF OF LEMMA 4.2


Since regret(t) is not larger than 1 in any case, R(T,b)≤∑_t=z_T^Tm_t, where
 {m_t}_t=z_T^T is a sequence of independent Bernoulli variables with 𝔼[m_t]=λ_1t. By Hoeffding's inequality,   

    ℙ(∑_t=z_T^Tm_t-∑_t=z_T^Tλ_1t>a)≤exp(-2a^2/T),

for any a≥ 0. Setting exp(-2a^2/T)=δ, we have a=√(Tlog(1/δ)/2). Hence, with probability at least 1-δ,

    ∑_t=z_T^Tm_t≤∑_t=z_T^Tλ_1t+√(T/2log(1/δ))≤∑_t=1^Tλ_1t+√(T/2log(1/δ)).

Since λ_1t=λ_1√(log(dt)/t), 

    ∑_t=1^Tλ_1t   =∑_t=1^Tλ_1√(log(dt)/t)≤λ_1T√(1/T∑_t=1^Tlog(dT)/t)≤λ_1√(T)√(log(dT))√(1+logT),

where the first inequality is due to Jensen's inequality and the second is due to ∑_t=1^T(1/t)≤ 1+∫_t=1^T(1/t)dt=1+logT.




§ PROOF OF LEMMA 4.3


Recall that we defined z_T=max(3/C(ϕ_1)^2logd, 1/C(ϕ_1)^2log(T^2/δ')) where C(ϕ_1)=min(0.5, ϕ_1^2/256s_0). Due to assumptions A2 and A3 and Corollary 3.4, we have with probability at least 1-δ', 

    Σ̂_t:=1/t∑_τ=1^tb̅(τ)b̅(τ)^T∈ C(supp(β), ϕ_1/√(2))   for all  t≥ z_T,i

where δ'<δ. It remains to show that when (<ref>) holds, the left-hand side of (8) is smaller than (δ-δ')/t^2. In Section 3.2, we have shown that given the conditioning argument in (8) and the restriction (7) on π_a(t)(t), (r̂(τ)-b̅(τ)^Tβ|ℱ_τ-1) is R̃-sub-Gaussian for all τ=1,⋯,t, with R̃=O(1). Applying Lemma 3.2 with (x_τ,y_τ)=(b̅(τ),r̂(τ)) for τ=1,⋯,t, ϕ=ϕ_1/√(2), R=R̃ and δ=(δ-δ')/t^2 completes the proof.  



§ PROOF OF LEMMA 4.4


Suppose t corresponds to subgroup (c-a). Since a(t)=1≤ i≤ Nargmax{b_i(t)^Tβ̂(t-1)} for this subgroup, (b_a(t)(t)-b_a^*(t)(t))^Tβ̂(t-1)≥ 0 and

    regret(t)   ≤ regret(t)+(b_a(t)(t)-b_a^*(t)(t))^Tβ̂(t-1)
       =(b_a(t)(t)-b_a^*(t)(t))^T(β̂(t-1)-β)
       ≤ ||b_a(t)(t)-b_a^*(t)(t)||_2||β̂(t-1)-β||_2
       ≤ ||β̂(t-1)-β||_2
       ≤ ||β̂(t-1)-β||_1 ≤ d_t,

where the second inequality is due to Cauchy-Schwarz inequality and the third inequality is due to assumption A1. Hence, the sum of regrets from subgroup (c-a) is at most ∑_t=1^Td_t, which we can bound as follows. 

    ∑_t=1^Td_t   ≤√(128)/ϕ_1^2s_0R̃√(log(edT^2/δ-δ'))∑_t=1^T√(1/t)
       ≤√(128)/ϕ_1^2s_0R̃√(log(edT^2/δ-δ'))T√(1/T∑_t=1^T1/t)≤√(128)/ϕ_1^2s_0R̃√(log(edT^2/δ-δ'))√(T)√(logT).

The derivation is analogous to that of the upper bound of  ∑_tλ_1t because d_t and λ_1t have the same order in t. Meanwhile, we proved in Lemma 4.3 that the subgroup (c-b) is empty with probability at least 1-δ. Therefore, with probability at least 1-δ,

    R(T,c)≤∑_t=1^Td_t ≤√(128)/ϕ_1^2s_0R̃√(log(edT^2/δ-δ'))√(T)√(logT).




§ PROOF OF THEOREM 4.1


Let R(T,a) be the sum of regrets from group (a). Due to R(T,a)≤ z_T, Lemma 4.2, and Lemma 4.4, we have with probability at least 1-2δ, 

    R(T)   ≤ R(T,a)+R(T,b)+R(T,c)
       ≤max(3/C(ϕ_1)^2logd, 1/C(ϕ_1)^2log(T^2/δ'))+√(128)/ϕ_1^2s_0R̃√(T)log(edT^2/δ-δ')+λ_1√(T)log(dT)
       +√(T/2log(1/δ))
       =O(s_0√(T)log(dT)).




