Information Directed Sampling for Sparse Linear Bandits
Year: 2022

Abstract:
Stochastic sparse linear bandits offer a practical model for high-dimensional online decision-making problems and have a rich information-regret structure. In this work we explore the use of information-directed sampling (IDS), which naturally balances the information-regret trade-off. We develop a class of informationtheoretic Bayesian regret bounds that nearly match existing lower bounds on a variety of problem instances, demonstrating the adaptivity of IDS. To efficiently implement sparse IDS, we propose an empirical Bayesian approach for sparse posterior sampling using a spike-and-slab Gaussian-Laplace prior. Numerical results demonstrate significant regret reductions by sparse IDS relative to several baselines.

heading: 1 Introduction
text: Standard linear bandits associate each action with a feature vector and assume the mean reward is the inner product between the feature vector and an unknown parameter vector [Auer, 2002, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010, Chu et al., 2011, Abbasi-Yadkori et al., 2011]. Sparse linear bandits generalize linear bandits by assuming the unknown parameter vector is sparse [Abbasi-Yadkori et al., 2012, Carpentier and Munos, 2012, Hao et al., 2020b] and is of great practical significance for modeling high-dimensional online decision-making problems [Bastani and Bayati, 2020]. Lattimore and Szepesvári [2020, §24.3] established a Ω( √ sdn) regret lower bound for the data-rich regime, where n is the horizon, d is the feature dimension, s is the sparsity and data-rich regime refers to the horizon n ≥ dα for some α > 0. This means polynomial dependence on d is generally not avoidable without additional assumptions. However, this bound hides much of the rich structure of sparse linear bandits by a crude maximisation over all environments.
When the action set admits a well-conditioned exploration distribution, Hao et al. [2020b] discovered the information-regret trade-off phenomenon by establishing an Θ(poly(s)n2/3) minimax rate for the data-poor regime. An interpretation for this optimal rate is that the agent needs to acquire enough information for fast sparse learning by pulling informative actions that even have high regret. Explore-then-commit algorithm can achieve this rate for the data-poor regime but is sub-optimal
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
in the data-rich regime. Therefore, our goal is to develop an efficient algorithm that can adapt to different information-regret structures for sparse linear bandits.
Contributions Our contribution is three-fold:
• We prove that optimism-based algorithms fail to optimally address the information-regret trade-off in sparse linear bandits, which results in a sub-optimal regret bound.
• We provide the first analysis using information theory for sparse linear bandits and derive a class of nearly optimal Bayesian regret bounds for IDS that can adapt to information-regret structures.
• To approximate the information ratio, we develop an empirical Bayesian approach for sparse posterior sampling using spike-and-slab Gaussian-Laplace prior. Through several experiments, we justify the great empirical performance of sparse IDS with an efficient implementation.

heading: 2 Preliminary
text: We first introduce the basic setup of stochastic sparse linear bandits. The agent receives a compact action set A ⊆ Rd in the beginning where |A| = K. At each round t, the agent chooses an action At ∈ A and receives a reward Yt = 〈At, θ∗〉 + ηt, where (ηt)nt=1 is a sequence of independent standard Gaussian random variables and θ∗ ∈ Rd is the true parameter unknown to the agent. We make the mild boundedness assumption that for all a ∈ A, ‖a‖∞ ≤ 1. The notion of sparsity can be defined through the parameter space Θ:
Θ = θ ∈ Rd ∣∣∣∣∣ d∑ j=1 1{θj 6= 0} ≤ s, ‖θ‖2 ≤ 1  . We assume s is known and it can be relaxed by putting a prior on it. We consider the Bayesian setting where θ∗ is a random variable taking values in Θ and denote ρ as the prior distribution. The optimal action is x∗ = argmaxa∈A E[〈a, θ∗〉|θ∗]. The agent chooses At based on the history Ft = (A1, Y1, . . . , At−1, Yt−1). Let D(A) be the space of probability measures over A. A policy π = (πt)t∈N is a sequence of deterministic functions where πt(Ft) specifies a probability distribution overA. The information-theoretic Bayesian regret of a policy π [Russo and Van Roy, 2014] is defined as
BR(n;π) = E [ n∑ t=1 〈x∗, θ∗〉 − n∑ t=1 Yt ] ,
where the expectation is over the interaction sequence induced by the agent and environment and the prior distribution over θ∗.
Notation Denote Id as the d × d identity matrix. Let [n] = {1, 2, . . . , n}. For a vector x and positive semidefinite matrix A, we let ‖x‖A = √ x>Ax be the weighted `2-norm and σmin(A) be the minimum eigenvalue of A. The relation x & y means that x is greater or equal to y up to some universial constant and Õ(·) hides modest logarithmic factors and universal constant. The cardinality of a setA is denoted by |A|. Given a measure P and jointly distributed random variables X and Y we let PX denote the law ofX and we let PX|Y be the conditional law ofX given Y : PX|Y (·) = P(X ∈ ·|Y ). The mutual information between X and Y is I(X;Y ) = E[DKL(PX|Y ||PX)] where DKL is the relative entropy. We write Pt(·) = P(·|Ft) as the posterior measure where P is the probability measure over θ and the history and Et(·) = E(·|Ft). Denote It(X;Y ) = Et[DKL(Pt,X|Y ||Pt,X)].

heading: 3 Related work
text: Sparse linear bandits Abbasi-Yadkori et al. [2012] proposed an inefficient online-to-confidenceset conversion approach that achieves an Õ( √ sdn) upper bound for an arbitrary action set. Lattimore
et al. [2015] developed a selective explore-then-commit algorithm that only works when the action set is exactly the binary hypercube and derived an optimal O(s √ n) upper bound. Hao et al. [2020b] introduced the notion of an exploratory action set and proved a Θ(poly(s)n2/3) minimax rate for the data-poor regime using an explore-then-commit algorithm. Hao et al. [2021] extended this concept to a MDP setting. Carpentier and Munos [2012] considered a special case where the action set is the unit sphere and the noise is vector-valued so that the noise becomes smaller as the dimension grows. We summarize the comparison of existing results with our work in Table 3.
Sparse linear contextual bandits It recently became popular to study the contextual setting, where the action set changes from round to round. These results can not be reduced to our setting since they rely on either careful assumptions on the context distribution [Bastani and Bayati, 2020, Wang et al., 2018, Kim and Paik, 2019, Wang et al., 2020, Ren and Zhou, 2020, Oh et al., 2020] such that classical high-dimensional statistics can be used, or have polynomial dependency on the number of actions [Agarwal et al., 2014, Foster and Rakhlin, 2020, Simchi-Levi and Xu, 2020].
Information-directed sampling Russo and Van Roy [2018] introduced IDS and derived Bayesian regret bounds for multi-armed bandits, linear bandits and combinatorial bandits. Liu et al. [2018] studied IDS for bandits with graph-feedback. Kirschner and Krause [2018], Kirschner et al. [2020a] investigated the use of IDS for bandits with heteroscedastic noise and partial monitoring. Kirschner et al. [2020b] proved the asymptotic optimality of frequentist IDS for linear bandits.
Information-theoretic analysis Russo and Van Roy [2014] introduced an information-theoretic analysis of Thompson sampling (TS) and Bubeck and Sellke [2020] strengthened the result with a first-order Bayesian regret analysis. Dong and Roy [2018], Dong et al. [2019] extended the analysis to infinite-many actions and logistic bandits. Lattimore and Szepesvári [2019] explored the use of information-theoretic analysis for partial monitoring. Lu and Van Roy [2019] generalized the analysis to reinforcement learning.
Bayesian sparse linear regression In the Bayesian framework, spike-and-slab methods are commonly used as probabilistic tools for sparse linear regression but most of prior works focus on variable selection and parameter estimation rather than uncertainty quantification [Mitchell and Beauchamp, 1988, George and McCulloch, 1993, Ročková and George, 2018]. Bai et al. [2020] provided a comprehensive overview.

heading: 4 Does the optimism optimally balance information and regret?
text: We demonstrate the necessity of balancing the trade-off between information and regret through a simple sparse linear bandit instance. We give an example where the optimal regret is only possible
by playing actions that are known to be sub-optimal. This phenomenon has disturbing implications for policies based on the principle of optimism, which is that they can never be minimax optimal in certain regime.
Illustrative example Consider a problem instance whereA = I ∪U is the union of an informative action set I and an uninformative action set U :
• I is a subset of the hypercube that has three properties. First, |I| = O(s log(ed/s)). Second, the last coordinate of actions in I is always -1. Third, the empirical covariance of the uniform distribution over I has a restricted minimum eigenvalue (Definition A.1) at least 1/4. We prove such I does exist in Appendix A.1 through a probabilistic argument.
• U = {x ∈ Rd|xj ∈ {−1, 0, 1} for j ∈ [d− 1], ‖x‖1 = s− 1, xd = 0}.
The true parameter θ∗ = (ε, . . . , ε, 0, . . . , 0,−1), where ε > 0 is a small constant.
Information-regret structure Sampling an action uniformly at random from I ensures the covariance matrix is well-conditioned so that sparse learning such as Lasso [Tibshirani, 1996] can be used for learning θ∗ faster than ordinary least squares. This means pulling actions from I provides more information to infer θ∗ than from U . On the other hand, actions from I lead to high regret due to the last coordinate -1. As a consequence, Hao et al. [2020b] has proven that the minimax regret for this problem is Θ(poly(s)n2/3) when the horizon is smaller than the ambient dimension.
Sub-optimality of optimism-based algorithms We argue the optimism principle does not take this subtle trade-off into consideration and yields sub-optimal regret in the data-poor regime. In general, optimism-based algorithms chooseAt = argmaxa∈Amaxθ̃∈Ct〈a, θ̃〉, where Ct ⊆ R
d is a confidence set that contains the true θ∗ with high probability. We assume that there exists a constant c > 0 such that Ct ⊆ {θ : (θ̂t − θ)>Vt(θ̂t − θ) ≤ c √ s log(n)}, where Vt = ∑t s=1AsA > s and θ̂t is some sparsity-aware estimator. Such confidence set can be constructed through an online-to-confidence set conversion approach [Abbasi-Yadkori et al., 2012]. Define Rθ(n;π) = E[ ∑n t=1〈x∗, θ〉 − ∑n t=1 Yt] for a fixed θ.
Claim 4.1. Let πopt be such an optimism-based algorithm. There exists a sparse linear bandit instance characterized by θ such that for the data-poor regime, we have
Rθ(n;π opt) & n/(log(n)s log(ed/s)) .
The proof is deferred to Appendix A.1. The reason is that optimism-based algorithms do not choose actions for which they have collected enough statistics to prove these actions are suboptimal, but in the sparse linear setting it can be worth playing these actions when they are informative about other actions for which the statistics are not yet so clear. This phenomenon has been observed before in linear and structured bandits [Lattimore and Szepesvari, 2017, Combes et al., 2017, Hao et al., 2020a].

heading: 5 Information-directed sampling
text: As shown by Hao et al. [2020b], although the explore-then-commit algorithm can achieve the minimax optimal regret in the data-poor regime, it suffers sub-optimal regret in the data-rich regime. This motivates us consider IDS.

heading: 5.1 Design principle of IDS
text: Unlike the optimism principle, IDS explicitly balances the amount of information it gains about the optimal action and expected single-round regret through minimizing a notion of information ratio. More formally, when playing action a, the information gain It(x∗;Yt,a) is the mutual information
between the optimal action and the reward the agent receives for taking action a, and the expected single-round regret is ∆t(a) := Et[〈x∗, θ∗〉 − 〈a, θ∗〉]. The information ratio is defined as
Ψt,λ(π) = (∆>t π) λ
I>t π , (5.1)
where we write ∆t ∈ R|A| and It ∈ R|A| as corresponding vectors. Then IDS takes the action according to πt = argminπ∈D(A) Ψt,2(π). Remark 5.1. The information ratio defined in Eq. (5.1) is a little more general than what Russo and Van Roy [2018] introduced which specified λ = 2. As observed by Lattimore and György [2020], the right value of λ depends on the dependence of the regret on the horizon.

heading: 5.2 Information-theoretic Bayesian regret bound
text: In this section, we derive a class of Bayesian regret upper bound for sparse IDS. We first define a notion of exploratory action set. Definition 5.2 (Exploratory action set). Let Cmin(A) = maxµ∈D(A) σmin(EA∼µ[AA>]). For an action set A, if Cmin(A) ≥ 11, we say A is exploratory.
We say that A has sparse optimal actions if the optimal action is s-sparse almost surely with respect to the prior. One can verify the action set of the hard instance developed in Hao et al. [2020b]2 is exploratory and has sparse optimal actions since sampling uniformly from the corner of informative action set shows that Cmin(A) ≥ 1 and the optimal actions always come from uninformative action set, which is sparse. Theorem 5.3 (Regret bound for sparse IDS). Suppose πIDS = (πt)t∈N where πt = argminπ Ψt,2(π). Let ∆ = min(log(K), 2s log(Cdn1/2/s)) for some absolute constant C > 0. For an arbitrary action set, the following regret bound holds
BR(n;πIDS) ≤ √ 1
2 nd∆ .
When A is exploratory and has sparse optimal actions, the following regret bound holds
BR(n;πIDS) ≤ min
{√ 1
2 nd∆,
s 2 3n 2 3 ∆ 1 3
(2Cmin(A)) 1 3
} .
This theorem shows the great adaptivity of IDS for sparse linear bandits in the sense that a single policy adapts to different information-regret structures. We summarize the regret bounds in a variety of of different regimes in Table 5.2. Remark 5.4. The explore-then-commit algorithm proposed by Hao et al. [2020b] for sparse linear bandits has O(poly(s)n2/3) regret bound when the action set is exploratory and it is known that this O(n2/3) rate is not improvable. Thus, it is sub-optimal for data-rich regime comparing with Θ( √ sdn) minimax rate. In contrast, IDS is nearly optimal in both regimes.
As a direct application of our analysis, we also include a novel Bayesian regret bound for sparse TS. Corollary 5.5 (Regret bound for sparse TS). For an arbitrary action set, the following regret bound holds for some absolute constant C > 0
BR(n;πTS) ≤ √ 1
2 ndmin(log(K), 2s log(Cdn1/2/s)) .
Proof of Theorem 5.3. We prove our main result in three steps. All the proofs of technical lemmas are deferred to the appendix.
1In the definition 1 is simply a convenient constant. More precisely, Cmin(A) is a problem-dependent parameter of our regret bound.
2The hard instance is almost the same as the one in illustrative example except the informative action set is a full hypercube.
Step 1: Generic Bayesian regret upper bound We define Ψ∗,λ ∈ R as the worse-case information ratio such that for each t ∈ [n], Ψt,λ(πt) ≤ Ψ∗,λ almost surely. Lemma 5.6. Suppose πIDS = (πt)t∈N where πt = argminπ Ψt,2(π). Then the following regret bound holds
BR(n;πIDS) ≤ inf λ≥2 21−2/λΨ 1/λ ∗,λ I(x ∗;Fn+1)1/λn1−1/λ ,
where Fn+1 refers to the history.
This lemma demonstrates the adaptivity of a single IDS for different information ratios. The choice of λ essentially trades off the information-ratio and the horizon.
Step 2: Bounding the worse-case information ratio We bound the worse-case information ratio for different λ. It shows that for certain action sets, the worse-case information ratio with λ = 3 could be much smaller than the one with λ = 2.
Lemma 5.7. For an arbitrary action set, we have Ψ∗,2 ≤ d/2. For an exploratory action set that has sparse optimal actions, we have Ψ∗,3 ≤ s2/(4Cmin(A)).
The bound of Ψ∗,2 essentially follows Russo and Van Roy [2014, Proposition 5] that bounds the information ratio of IDS by TS. And Ψ∗,3 is bounded by the information ratio of a mixture policy πmixt = (1− γ)πTSt + γµ where µ is an exploratory policy such that σmin(EA∼µ[AA>]) is a constant and the mixture rate γ ≥ 0 is optimized to minimize the bound.
Step 3: Bounding the mutual information The mutual information I(x∗;Fn+1) quantifies the cumulative information gain about the optimal action. Russo and Van Roy [2014, 2018] naively bound this term by entropy H(x∗), which can be arbitrarily large or even infinite for some priors. Instead, we bound this term by the mutual information between the true parameter and the history through data-processing lemma.
Lemma 5.8. I(x∗;Fn+1) ≤ I(θ∗;Fn+1) ≤ min{log(K), 2s log(Cdn1/2/s)}.
Our proof is based on the metric entropy of the parameter space and square root KL-divergence that is commonly used in information-theoretic lower bound analysis [Yang and Barron, 1999]. As a by-product of our analysis, by setting s = d, our analysis recovers the Õ(d √ n) Bayesian regret bound for TS under linear bandits with infinitely many actions without using rate-distortion theory [Dong and Roy, 2018]. Combining Lemmas 5.6-5.8 yields our conclusion.

heading: 6 Computational methods
text: In this section, we provide an efficient implementation of sparse IDS. The main challenge is to generate posterior samples in a computationally efficient manner to approximate the information ratio. Due to the lack of conjugate prior, we propose an empirical Bayesian approach for sparse sampling with spike-and-slab priors.

heading: 6.1 An empirical Bayesian approach for sparse sampling
text: In the Bayesian framework, the golden standard for modeling θ∗ is to place spike-and-slab priors [Mitchell and Beauchamp, 1988]. With a hierarchical structure over the parameter and model space,
vanilla spike-and-slab priors usually have the following form
ρ(θ|γ, σ2) = d∏ j=1 [γjψ1(θj , σ) + (1− γj)ψ0(θj , σ)] , ρ(γ|β) = d∏ j=1 βγj (1− β)1−γj , (6.1)
where γ = (γ1, . . . , γd)> is an intermediate binary vector that indexs the 2d possible models and β ∈ [0, 1] denotes a priori fraction of relevant variables among all the parameters. In particular, ψ1(θ, σ) serves as a slab distribution to models relevant variables and ψ0(θ, σ) is a point mass at zero that serves as a spike distribution to model irrelevant variables. Remark 6.1. It is typical to assume β follows a Beta prior as β ∼ Beta(a, b) and variance σ2 follows an inverse gamma prior ρ(σ2) = IG(ν/2, νλ/2) with ν = 1 and λ = 1 (Rořková and George [2014]). For simplicity, we do not impose those additional layers of priors.
Prior specification. Although the prior in Eq. (6.1) is theoretically sound, exploring the full posterior in high-dimensions over the entire model space using point-mass spike-and-slab priors can be computationally prohibitive. Therefore, the spike distribution is usually relaxed as a small-scale Gaussian distribution [Rořková and George, 2014] or Laplace distribution [Ročková and George, 2018]. Thus, we consider a spike-and-slab Gaussian-Laplace prior that inherits the property of the Lasso [Tibshirani, 1996] for variable selection while the Gaussian component avoids the potential over-shrinkage effect. Each component of the prior is specified as
ψ0(θ, σ) = 1
2σλ0 exp ( − |θ| σλ0 ) , ψ1(θ, σ) = 1√ 2πσ2λ1 exp ( − θ 2 2σ2λ1 ) ,
where λ0 > 0 denotes a scaling parameter that encourages the shrinkage of irrelevant parameters and λ1 is often set to a large value for a standard regularization [Rořková and George, 2014].
An empirical Bayesian approach. Suppose L(Fn+1|θ, σ2) is the likelihood function where Zn is the historical data. According to the Bayes rule, the full posterior follows
p(θ,γ|Fn+1, σ2, β) ∝ L(Fn+1|θ, σ2)ρ(θ|γ, σ2)ρ(γ|β) . (6.2) To speed up the sampling, we only sample θ and optimize γ with respect to the posterior instead. To tackle this issue of the binary vector γ, we consider a continuous relaxation by introducing a latent vector ν ∈ [0, 1]d as the probability of the variable being included in the model. We focus on the simulations of the conditional expectation of the complete posterior:
Eγ|· [ log p(θ,γ|Fn+1, σ2, β) ] = logL(Fn+1|θ, σ2) + Eγ|· [ log ρ(γ|β) + log ρ(θ|γ, σ2) ] + C1 ,
where C1 is the normalizing constant and Eγ|·[·] denotes the the conditional expectation with respect to γ given the current parameter θ. Then we compute
Eγ|· [log ρ(γ|β)] = d∑ i=1 Eγ|· [γi log(β) + (1− γi) log(1− β)] = d∑ i=1 log ( β 1− β ) νi + C2 ,
where C2 = d log(1− β) and νi = Eγ|·[γi] denotes a conditional probability. By the Bayes rule, we have
νi = P(γi = 1|θi, β) = ρ(θi|γi = 1)P(γi = 1|β)
ρ(θi|γi = 1)P(γi = 1|β) + ρ(θi|γi = 0)P(γi = 0|β) . (6.3)
For the mixture prior, we optimize the variational lower bound
Eγ|·[log ρ(θ|γ, σ2)] ≥ d∑ j=1 −1− νj λ0 |θj | σ − νj λ1 θ2j 2σ2 + C3 ,
where the inequality follows by Jensen’s inequality and C3 denotes a trivial constant.
We summarize the full sampling procedure in Algorithm 1. Given a current estimate of (θ(k), ν(k)) at step k and Fn+1, we adapt an empirical Bayesian method [Deng et al., 2019] by iteratively sampling θ based on the negative log-posterior with adaptive priors
Q(θ|θ(k), ν(k),Fn+1) = − logL(Fn+1|θ, σ2) + d∑ i=1 ( 1− ρi λ0 |θi| σ + ρi λ1 θ2i 2σ2 ) ,
and optimizing the conditional probability ν through stochastic approximation algorithms (Robbins and Monro [1951]) until the equilibrium is achieved. Remark 6.2. Algorithm 1 will need to output M posterior samples. Suppose we run a Markov Chain for 100 steps (k = 1, 2, . . . , 100) and want 10 posterior samples. Setting the thinning factor T = 10 means every 10 steps, we pick a θk as the required posterior sample, e.g., θ10, θ20, . . . , θ100.
Algorithm 1 Empirical Bayesian sparse sampling 1: Input: dataset Fn+1, learning rate (ηk), step size (ωk), a priori knowledge of σ2 and β, thinning
factor T , number of posterior samples M , regularization parameters λ0, λ1. 2: Initialize: θ(0) ∼ N(0, 0.1Id) and ν(0) = (0.5, . . . , 0.5)>. 3: for k ≥ 1 do 4: Sampling step: θ(k+1) = θ(k) − ηk ∂∂θQ(θ|θ (k), ν(k),Fn+1) + √ 2ηkξ (k), where ξ(k) is a standard Gaussian random vector. 5: Stochastic approximation step: ν(k+1) = (1 − ωk)ν(k) + ωkν, where ν is derived from Eq. (6.3). 6: end for 7: Output: M posterior samples θ(T ), θ(2T ), . . . , θ(MT ).

heading: 6.2 Optimize the information ratio
text: For sparse linear bandits, it is expensive to estimate and optimize the original information ratio that involves the calculation of KL-divergence. Following Section 6.3 in Russo and Van Roy [2018], we optimize a variance-based information ratio instead: πt = argminπ(∆ > t π)
2/(2v>t π), where we define vt(a) = Et[a>Et[θ∗|x∗] − a>Et[θ∗]]2 for each a ∈ A. With sufficient number of posterior samples of θ∗ produced by Algorithm 1, we can accurately estimate Et[θ∗|x∗],Et[θ∗] and the information ratio. The detailed procedure is deferred to Appendix B. For the optimization step, we simply choose the action who can has the minimum per-action variance-based information ratio to accelerate the computation. The overall algorithm can be found in Algorithm 2.
Algorithm 2 Sparse IDS 1: Input: time horizon n, action set A, number of posterior samples per round M . 2: for t = 1, · · · , n do 3: Obtain M posterior samples θ1, . . . , θM by Algorithm 1. 4: Calculate ∆̂t ∈ R|A| and v̂t ∈ R|A| using Algorithm 3 in Appendix B. 5: Take the action At = argmina∈A ∆̂ 2 t (a)/v̂t(a) and receive a reward: Yt = 〈At, θ∗〉+ ηt.
6: end for
Remark 6.3. While sparse IDS is computationally efficient, we only have samples from approximate posterior distribution rather than the exact one. This will incur a non-negligible approximation error that may depend linearly on the time horizon. This is observed previously by analyzing approximate Thompson sampling [Lu and Van Roy, 2017] or more recently for IDS [Lu et al., 2021].

heading: 7 Experiments
text: First, we evaluate the performance of the empirical Bayesian sparse sampling procedure for generating posterior samples through an offline sparse linear regression. We set d = 10, s = 3, n = 100 and the actions are drawn i.i.d from a multivariate normal distribution N(0,Σ) with Σij = 0.6|i−j|. The true parameter is θ∗ = (3, 2, 0, 0, . . . , 0) ∈ R10. We plot the empirical posterior distributions as well as their posterior mean for the first three covariates in Figure 1. It shows that the posterior distribution concentrates well around the true value and the algorithm identifies the sparse pattern quickly.
Second, we evaluate sparse IDS with several other competitors. In particular, we compare with LinUCB [Abbasi-Yadkori et al., 2011], LinTS with Gaussian prior [Agrawal and Goyal, 2013], IDS
for linear bandits (Algorithm 6 in Russo and Van Roy [2018]) and ESTC [Hao et al., 2020b]. Note that the first three algorithms are not sparsity-aware. Our sparse sampling procedure naturally induces a sparse TS algorithm so we include it into comparison.
Setting All the true parameters are randomly generated from a multivariate normal distribution, truncated to be sparse and normalized to have square norm 1. The noise variance is fixed to be 2 and we replicate the experiments over 200 trials. We plot the empirical cumulative Bayesian regret. Each Bayesian algorithm will take 10000 posterior samples. We use the TS without blow-up factor for the variance and tune the length of confidence interval of LinUCB over a candidate set.
Hard sparse linear bandits instance Consider the hard problem instance introduced in Section 4 that includes informative and uninformative action sets and set d = 10, s = 2. For each trial, we record the number of pulls of sparse TS and sparse IDS for informative actions. We draw the histogram of number of pulls during 200 trial in Figure 2. It is clear that IDS tends to invest more on the informative action sets but suffer less regret than TS if there exists an information-regret trade-off phenomenon.
Multivariate Gaussian action set We consider a more general case where each action is generated from multivariate normal distribution N(0,Σ) with Σij = 0.6|i−j|. The number of actions K is fixed to be 200 and the level of sparsity s/d is fixed to be 0.1. We report the results in Figure 3 for d = 20, 40, 100. It is obvious that sparse IDS consistently outperforms other algorithms and the improvement increases as the feature dimension increases.

heading: 8 Conclusion
text: In this work, we investigate the theoretic and practical applicability of information-directed sampling for sparse linear bandits. An interesting future direction is to extend similar ideas to sparse linear contextual bandits.

heading: Acknowledgement
text: We thank Yoan Russac, Dorian Baudry and Alexandre Filiot for making their code of informationdirected sampling public.

Review summaries:
The paper studies a high-dimensional linear bandit problem with sparse structure. The authors propose information-directed sampling (IDS), which naturally 4 balances the information-regret trade-off. They establish information-theoretic Bayesian regret bounds that nearly match existing lower bounds. For the implementation of sparse IDS, the authors propose an empirical Bayesian approach for sparse posterior sampling using a spike-and-slab Gaussian-Laplace prior. The numerical experiments show that the proposed method is more effective compared to the existing methods.

The paper considers the sparse linear bandit problem from Bayesian perspective. The authors show that IDS achieves optimal Bayesian regret bounds for both data-poor and data-rich regime. Since their algorithm cannot be implemented efficiently, they propose an algorithm desired to approximate the IDS, which is shown to work well empirically. 

 This paper analyses information-directed sampling (IDS) for the problem of sparse linear bandits. They identify a key issue limiting optimism-based algorithms (or UCB type methods) where, for certain sparse instances, the regret can scale nearly linearly in the time horizon. They demonstrate that IDS does circumvents this information obstacle, by explicitly choosing actions that optimize for the information ratio: i.e. a ratio between the (sub)optimality of the action chosen and the future information gleaned from it. For IDS, they demonstrate an adaptive result, that shows its (up to log factors) optimality in regret both  for short (data-poor) and long (data rich) time horizons. Computationally, IDS is non-trivial to implement in the sparse setting, for which the authors propose approach using mcmc sampling, borrowing from Bayesian sparse linear regression literature.