Information Directed Sampling for Sparse Linear Bandits
Authors: Botao Hao
Tor Lattimore
Wei Deng
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Information-directed sampling
sparse linear bandits
Bayesian regret

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 information-theoretic 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.


Information Directed Sampling for Sparse Linear Bandits
Botao Hao
Tor Lattimore Deepmind latt.imore@google.comm com
Deepmind haobotao000@gmail.com
Wei Deng
Department of Mathematics
Purdue University
weideng0566@gail.. com
Abstract
Stochastic sparse linear bandits offer practical model for high-dimensional online decision-making problems and have rich information-regret structure. In this work explore the use of informetioondirrcteddd sampling (IDS), which naturally balances the information-regret trade-off. We develop class of information- theoretic 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-slat Gaussian-Laplace prior. Numerical results demonstrate significant regret reductions by sparse IDS relative several baselines.
Introduction
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 al., 2008, Rusmevichientong and Tsitsiklis, 2010, Chu al., 201 1, Abbasi- Yadkori et al., 201 1]. Sparse linear bandits generalize linear bandits by assuming the unknown parameter vector is sparse Labbasi-Yadkoyg 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 Szepesvári [2020, $24.3) established (iVV9(VV)) regret lower bound for the regime, where is the horizon, d is the feature dimension, is the sparsity and data-rich regime refers to the horizon 2 da 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 [2020b] discovered the information-regee reegret trade-off phenomenon by establishing an ((poly(s)n) the data-poor regime. An interpretation for this optimal rate is that the agent needs 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
minimax rate for
35th Conference 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 informetion-regret structures for sparse linear bandits.
Contributions Our contribution is three-fold:
We prove that optimism-based algorithms fail to optimally address the information- 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 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 Gaussian-Laplace prior. Through several experiments, we justify the great empirical performance of sparse IDS with an efficient implementation.
Preliminary
We first introduce the basic setup of stochastic sparse linear bandits. The agent receives a compact action set A C Rd in the beginning where |A| K. At each round the agent chooses action A, A and receives reward Y, = (A,, )0) + Tr, where (nx) is sequence of independent standard Gaussian random variables and l* R is the true parameter unknown to the agent. We make the mild boundedness assumption that for all a E A. ||a] < 1. The notion of sparsity can be defined through the parameter space O:
E Rd Σ 110, + 03 S 10 1
We assume is known and it can be relaxed by putting a prior on it. We consider the Bayesian setting where 8 is random variable taking values in @ and denote p as the prior distribution. The optimal action is x² argmaxae.l [a, 0*) The agent chooses A, based on the history Y--1). Let D(A) be the space of probability measures over A. A policy = (TT)eN is a sequence of deterministic functions where (F(Fi) specifies a probability distribution over A. The information-thhoree Bayesian regret of policy x [Russo and Van Roy, 2014] is defined
F, = ................................
as
BM (n; T) =
Σ x
0-)
Σx:
1=1
where the expectation is over the interaction sequence induced by the agent and environment and the prior distribution over 6"
Notation Denote Ia the d x d identity matrix. Let [n]
For a vector and positive semidefinite matrix A, we let ||ж|| = Vx Az be the weighted f2-norm and mmin (A) be the minimum eigenvalue of A. The relation x Z y means that is greater or equal up some universial constant and (-) hides modest logarithmic factors and universal constant. The cardinality of set A denoted by [A]. Given a measure IP and jointly distributed random variables X and we let IPx denote the law of X and let P Exjy be the conditional law of X given Y: I (x) P(X (Y). The mutual information between X and is I(X; Y) EE (IP x |['x] where DKL is the relative entropy. We write (-) [P.)FF) as the posterior measure where P is the probability measure over 0 and the history and E.(.) = B.- Denote I,(X; Y) E, (Di. x IlP,) IlPr,x))
3
Related work
Sparse linear bandits Abbasi- Yadkori al. [2012] proposed an inefficient online-to-conn coon-ddeeneee set conversion approach that achieves an ((Vsd) upper bound for arbitrary action set. Lattimore

---

Table 1: Comparisons with existing results. APSI1, LCSI5, HLW20 refer to Abbasi-Yadkori et al. [2012], Lattimore et al. [2015], Hao et al. [2020b] accordingly. Exploratory action set is defined in Definition 5.2 and K is the number of actions. The last lower bound developed in Hao et al.
[2020b].
Action set
Algorithm
Type
Rate
APSI1
arbitrary
online-to- cocofiieence
freq
O(vsdn)
LCSI5
hypercube
elimination
freq
((syn)
HLW22
exploratory
explore-hen-coommit
freq
((s2/9n2/3)
This paper
arbitrary
sparse IDS
Bayesian
O v /sn,, /dn log (K) (K))
This paper
arbitrary
sparse TS
Bayesian
O(min( v sdn, v dn log(K)))
This paper
exploratory
sparse IDS
Bayesian
O(min( 2/333 2/3 vsdu)
Lower bound
arbitrary
NA
minimax
Ω adr)
Lower bound
exploratory
NA
minimax
(mmin(s (/ /d))
et al. [2015] developed a selective explore-then senee-the--commii algorithm that only works when the action set is exactly the binary hypercube and derived an optimal (ss/n) upper bound. Hao et al. [2020b] introduced the notion an exploratory action set and proved a ((poly(s) (/)) minimax rate for the data-poor regime using an explore-then-commi algorithm. Hao et al. [2021] extended this concept to MDP setting. Carpentier and Munos [2012] considered special case where the action set the unit sphere and the noise is vector-valued that the noise becomes smaller 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 not be reduced 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-directél 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- Kirschner and Krause [2018], Kirschner 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-theoreeii analysis Russo and Van Roy [2014] introduced an information-theome
analysis of Thompson sampling (TS) and Bubeck and Sellke [2020] strengthened the result with first-order Bayesian regret analysis. Dong and Roy [201 8), Dong et al. [2019] extended the analysis to infinite-many actions and logistic bandits. Lattimore and Szepesvári [2019] explored the use of information-theorete 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 com- monly 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, Ročková and George, 2018]. Bai et al. [2020] provided comprehensive overview.
4 Does the optimism optimally balance information and regret?
We demonstrate the necessity of balancing the trade-off between information and regret through simple sparse linear bandit instance. We give example where the optimal regret is only possible
3

---

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 where A = IUW is the union of an informative action set and an uninformative action set 21:
Z. is a subset of the hypercube that has three properties. First, | = O(s log(ed/s)) s)). Second, the last coordinate of actions is always -1. Third, the empirical covariance of the uniform distribution over has a restricted minimum eigenvalue (Definition A.I) at least 1/4, We prove such I does exist in Appendix A.1 through a probabilistic argument.
. U {Ir E R Iry E 1-1,0,17 1} for E [d 1], || = s 1, 0}.
The true parameter f* = (E, ............. c,0, o,................ 0, - 1), where e >> 0 is small constant.
Information-regee structure Sampling action uniformly at random from I ensures the covari- ance matrix is well-conditioned so that sparse learning such as Lasso [Tibshirani, 1996] can be used for learning 8* faster than ordinary least squares. This means pulling actions from I provides more information to infer /* than from 2. 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())n2/3) when horizon is smaller than the ambient dimension.
Sub-optimality of optimismm based algorithms We argue the optimism principle does not take this subtle trade-off into consideration and yields sub-optimal regret the data-poor regime. general, optimism basseddd---dddd--- algorithms choose A, argmax, maxăec, (a, 0), where C RR. is confidence that contains the 0" with high probability. We assume that there exists constant such that C, S (0: (0. 0) V. 0) I ev log(n)), where V, E A.A! and 0 is some sparsity- aware estimator. Such confidence set can be constructed through online-to-confidenee set conversion approach [Abbasi- Yadkori et al., 2012]. Define Rg(n; X) E E (x", (e",,) A) Ei= Yil for a fixed
Claim 4.1. Let nP be such an optimism aptieism-based algorithm. There exists sparse linear bandit instance characterized by 0 such that for the data- poor regime, we have
Rg (n; n opr) Σ n nn/(og(n)ssoog(ed/)
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 clear. This phenomenon has been observed before in linear and structured bandits [Lattimore and Szepesvari, 2017, Combes et al., 2017, Hao al., 2020a].
5 Information-directer sampling
As shown by Hao et al. [2020b], although the explore-then-commi 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.
5.1 Design principle of IDS
Unlike the optimism principle, IDS explicitly balances the amount of information it gains about the optimal action and expected single-round regret through minimizing notion of information ratio. More formally, when playing action the information gain le(x;; Yr.o) is the mutual information

---

For an between the optimal action and the reward the agent receives for taking action and the expected single-round regret is (a) := Eel(2" 07) (a, )- The information ratio is defined as
(4. m) V (
(5.1)
1 π
where we write 4, E RIAI and I TRAAI as corresponding vectors. Then IDS takes the action according to ae (T,((T).
Remark 5.1. The information ratio defined Eq. (5.1) is a little more general than what Russo and Van Roy [2018] introduced which specified À 2. As observed by Lattimore and György [2020], the right value of depends on the dependence the regret on the horizon.
5.2 information-theoretl Bayesian regret bound
In this section, we derive a class of Bayesian regret upper bound for sparse IDS. We first define notion of exploratory action Definition 5.2 (Exploratory action set). Let Cmin (A) max mmin (aaa))))iin(Balaaaa (BA>)[AA") action set A, if Ciin (A) 1', we say A is exploratory.
We say that A has sparse optimal actions if the optimal action s-sparse almost surely with respect to the prior. One can verify the action set of the hard instance developed in Hao al. [2020b] exploratory and has sparse optimal actions since sampling uniformly from the corner informative action set shows that Cmin 2 and the optimal actions always come from uninformative action set, which is sparse.
Theorem 5.3 (Regret bound for sparse IDS). Suppose π (TT)eN where T. argmin, ( Let A (ainloo((4 2s log( (/dn///s)) for some absolute constant C' >> 0. For an arbitrary action set, the following regret bound holds
BR nz π IDS
nds.
When A is exploratory and has sparse optimal actions, the following regret bound holds
sin A
BR; mD))
min
Ind
(2Cmin (A))
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 al. [2020b] for sparse linear bandits has (spolyss)n regret bound when the action set is exploratory and it known that this (nn2/3) rate is not improvable. Thus, it sub-optimal for data-rich regime comparing with O V sdn) minimax rate. In contrast, IDS is nearly optimal in both regimes.
As direct application 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
BA π T5) $ V nd minmingooo (K), 2s log(Cdn)///s)))
Proof of Theorem 5.3. We prove our main result in three steps. All the proofs technical lemmas are deferred to the appendix.
'In the definition simply a convenient constant. More precisely, Cain (A) is problem-dependent parameter of our regret bound.
"The hard instance almost same as the one illustrative example except informative action set a full hypercube.
5

---

Table 2: Summary of regret bounds of IDS for different regimes. Data-rich regime refers to d A/ss* and large K refers to K 2 dcxp(s).
Arbitrary action set
Exploratory (data-rich)
Exploratory (data-poor)
Large K
O(Vnds)
((Vnds)
Õ (sn
Small K
(()n)log(K)
O ((Vnd (og(K)
(s log (K))
Step 1: Generic Bayesian regret upper bound We define V.,A IR the worse-case informa- fion ratio such that for each E [n.]. (e,)(Te) s ..,x almost surely.
Lemma 5.6. Suppose TIDS (Te))en where Te argmin, (1,((T). Then the following regret bound holds
(n; mS)] inf 2 2/2 2/2 X22
1(x'(( A
where Fn41 refers the history.
This lemma demonstrates the adaptivity of 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 A. 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 V..2 S d/2. For an exploratory action set that has sparse optimal actions, we have v. 3 S 8² /²/(( (AA)).
The bound of V., essentially follows Russo and Van Roy [2014, Proposition 5] that bounds the information ratio of IDS by TS. And Va,a is bounded by the information ratio of a mixture policy Th = (1 - m TS + 7 where is an exploratory policy such that miinnE [AA [] is constant and the mixture rate y 2 0 is optimized minimize the bound.
Step 3: Bounding the mutual information The mutual information ;(="; quantifies the cumulative information gain about the optimal action. Russo and Van Roy [2014, 2018] naively bound this term by entropy Hxx"), which can be arbitrarily large even infinite for some priors. Instead, we bound this term by the mutual information between the true parameter and the history through data- pittearrocsssng lemma.
Lemma 5.8.
Fn++1) I(0"; I min(log(K)) (), 2s (Cdn /3/s))
Our proof is based on the metric entropy of the parameter space and square root KL-divergence that is commonly used in information-theorrtiee lower bound analysis [Yang and Barron, 1999]. As by- by-product of our analysis. by setting d, our analysis recovers the (ld/%) 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.
6 Computational methods
In this section, provide an efficient implementation of sparse IDS. The main challenge is to generate posterior samples in computationally efficient manner to approximate the information ratio. Due to the lack of conjugate prior, we propose empirical Bayesian approach for sparse sampling with spike-and-slab priors.
6.1 An empirical Bayesian approach for sparse sampling
In the Bayesian framework, the golden standard for modeling 0- is to place spike-and-slab priors [Mitchell and Beauchamp. 1988]. With hierarchical structure over the parameter and model space,

---

vanilla ppike-and-slab priors usually have the following form
p10 of) = (1 (1,,,,,0,_,)0(_,,,,,000,,,,,,,,,
II 8hh (1 1)1- j=1
(6.1)
j=1
where 7= (n...... 7a)" is intermediate binary vector that indexs the 2d possible models and 33 E [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 Vu(0, or) is a point mass at zero that serves as a spike distribution to model irrelevant variables.
Remark 6.1. It typical to assume 3 follows Beta prior as Beta(a, b) and variance o² follows and (Rofková and George (2014)).
an inverse gamma prior p(a?) IG(v/2, 2\/2) with 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 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 [Ročková and George, 2014] Laplace distribution [Ročková and George, 2018]. Thus, we consider spike-and-slaz 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 o) A0 exp
(-
add th (8,
2TTO~11 exp
20
where Ao > 0 denotes a scaling parameter that encourages the shrinkage of irrelevant parameters and A1 is often set to large value for a standard regularization [Rořková and George, 2014].
An empirical Bayesian approach. Suppose L(Fn 10,a²) is the likelihood function where Zn is the historical data. According to the Bayes rule, the full posterior follows
y00,1|m+1,.0 o², (3 C(F )2,, (()33))
(6.2)
To speed up the sampling, we only sample 9 and optimize y with respect the posterior instead. To tackle this issue of the binary vector 7, consider continuous relaxation by introducing latent vector [0, 1]d the probability of the variable being included in the model. We focus the simulations of the conditional expectation of the complete posterior:
Ey/- p(0 F2 .)] = log [(F o²) + Eyg [log p(>1))) + log p(0/7,00) + Ci,
where Ci is the normalizing constant and Egy-- [+] denotes the the conditional expectation with respect to y given the current parameter f. Then compute
B E. [log p(>]3)]] Σ Byl ly log(3) (1 7s) log(1 -31 = Σ log 1-
24 + C2.
3
where C2 = dloo(1 - 3) and vn 1xe] denotes conditional probability. By the Bayes rule, we have
p(0.1% 1)P(% 11.)
4 P(7 110,,8) -00 =
(6.3)
1 + p(0:)7% 0)P(( = 013)
For the mixture prior, we optimize the variational lower bound
d 1-
0
Vj 83
Ey [lo ((0 o²) Σ
+ Cs
Ao
20
where the inequality follows by Jensen's 's inequality and C3 denotes trivial constant.
We summarize the full sampling procedure in Algorithm 1. Given a current estimate of (Ø(k), ((() at step i and F,+1, we adapt an empirical Bayesian method [Deng al., 2019] by iteratively sampling 0 based on the negative pog-portrroor with adaptive priors
1(0)0(k), (())) FF = log C(Fa1100000000000
P
10.1
Pi
07
An
A1
2
7

---

and optimizing the conditional probability through stochastic approximation algorithms (Robbins and Monro [1951]) until the equilibrium is achieved.
Remark 6.2. Algorithm 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, pick t as the required posterior sample, e.g., @10 020 ,..., ....,01000 0
Algorithm 1 Empirical Bayesian sparse sampling
1: Input: dataset Fu+1. learning rate (mz), step size (WL). priori knowledge of o² and 8, thinning factor 7", number of posterior samples M, regularization parameters λo, A1.
2: Initialize: ((0) ~ (0, 0.1Ia) and v() = (0.5.....
3: for 2 1 do
4: Sampling step: g(k+1) ((k) тe ae Q(0(0(K) v()), Fu+11) + 22tEs(h), where g(A) is
standard Gaussian random vector.
wk)(lk) (K) + way, where is derived from 7: Output: M posterior samples 0(2T) ..... ((MT).
5: Stochastic approximation step: (k++))
Eq. (6.3).
6: end for
6.2 Optimize the information ratio
For sparse linear bandits, is expensive to estimate and optimize the original information ratio that involves the calculation of KL-divergence. Following Scction 6.3 in Russo and Van Roy [2018], we optimize cariance-based information ratio instead: Te = argmin, y (/TTT)/((2))) T), where define v. (a) E, (a E. [0" [=]] E,, [0=]]² for each a E A. With sufficient number of posterior samples of 0* produced by Algorithm
accurately estimate [0*[[=))) T. (0*) 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-basee 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 1,... , do
3: Obtain M posterior samples 0² ..... OM by Algorithm 1.
4: Calculate A, E RIAI and 0, E I RIAI using Algorithm in Appendix B.
5: Take the action A, = argmin (a) and receive a reward: Y; = (Ac, + m..
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 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].
Experiments
First, 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 multivariate normal distribution (00, Σ) with E, = 0- The true parameter is 0* = (3, 2, 0, .,.,,..))) 0) E 10 We plot the empirical posterior distributions as well as their posterior mean for the first three covariates in Figure 1. 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, compare with LinUCB [Abbasi- Yadkori et al., 2011], LinTS with Gaussian prior [Agrawal and Goyal, 2013), IDS

---

POSEnOr oignaaaton ch
Natornrr scabbicen
Pistoner OCTrO
175
1.5
20
05
Figure 1: Posterior distributions for the first three coordinates. The red lines are posterior means.
sard Instorce, d0116
32878
Scare 15
120
Figure 2: The left panel is the cumulative regret and the right panel is the histogram of number of pulls for informative actions. It's clear that sparse TS does not value information enough as it should.
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 be sparse and normalized have square norm The noise variance is fixed 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 candidate set.
Hard sparse linear bandits instance Consider the hard problem instance introduced in Section that includes informative and uninformative action sets and set d 10, 8 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 It clear that IDS tends invest more on the informative action sets but suffer less regret than TS if there exists an information-regre trade-off phenomenon.
Multivariate Gaussian action set We consider a more general case where each action is generated from multivariate normal distribution N Σ) with Σij 0.6/--il. The number of actions K is fixed to 200 and the level of sparsity s/d fixed to 0.1. We report the results in Figure 3 for d 20, 40, 100. obvious that sparse IDS consistently outperforms other algorithms and the improvement increases the feature dimension increases.
Mclivaritte daussenn
Nottvasttt Caundan, d2
LPFCE
1500
1770
06
Seams sprssics
Sgacs 811
1577
Spare E5
Tire
Figure 3: Cumulative regret for d 20, 40, 100.

---

8 Conclusion
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.
Acknowledgement
We thank Yoan Russac, Dorian Baudry and Alexandre Filiot for making their code of information- directed sampling public.
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312 2320, 2011.
Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-commiddenc-sst conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638 1646. PMLR, 2014.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
Peter Auer. Using confidence bounds for exploitation-exxploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Ray Bai, Veronika Rockova, and Edward I George. Spike-and-slah meets lasso: A review of the spike-and-slab lasso. arXiv preprint arXiv:2010.06451, 2020.
Hamsa Bastani and Mohsen Bayati. Online decision making with high lige-dimensional covariates. Operations Research, 68(1):276-294, 2020.
Sébastien Bubeck and Mark Sellke. First-order bayesian regret analysis of thompson sampling. In Algorithmic Learning Theory, pages 196-23 PMLR, 2020.
Alexandra Carpentier and Rémi Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics, pages 190-198. 2012.
Wei Chu, Lihong Li. Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208 224, 2011.
Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems, pages 1763-1771, 2017.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic lincar optimization under bandit feedback. 2008.
Wei Deng, Xiao Zhang, Faming Liang, and Guang Lin. An adaptive empirical bayesian method for sparse deep learning. Advances in neural information processing systems, 2019:5563, 2019.
Shi Dong and Benjamin Van Roy. An information-theoretie analysis for thompson sampling with many actions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4161 4169, 2018
Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance thompson sampling on logistic handits. In Conference Learning Theory, pages 1158-18 1160. PMLR, 2019.
10

---

Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression
oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Edward I George and Robert E McCulloch. Variable selection via gibbs sampling. Journal of the American Statistical Association, 88(423)8881888 1993.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in lincar contextual bandit. AISTATS, 2020a.
Botao Hao, Tor Lattimore, and Mengdi Wang. High- dimensional sparse linear bandits. Advances Neural Information Processing Systems, 33, 2020b.
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 316-324. PMLR, 2021.
Adel Javanmard and Andrea Montanari. Confidence intervals and hypothesis testing for high-dimensional regression. The Journal of Machine Learning Research, 15(1):2869 2909, 2014.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, pages 5869 5879, 2019.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358-384. PMLR, 2018.
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling linear partial monitoring. In Conference on Learning Theory, pages 2328-2369. PMLR, 2020a.
Johannes Kinsehner, Tor Lattimore, Claire Vemnade, and Csaba Szepesvári. Asymptotically optimal information- directed sampling, arXiv preprint arXiv:201 1.05944, 2020b.
Tor Lattimore and András György, Mirror descent and the information ratio. arXiv preprint arXiv:2009. 122288 2020.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. Artificial Intelligence and Statistics, pages 728-737, 2017.
Tor Lattimore and Csaba Szepesvári. An ineornation-theorrtiicc approach to minimax regret in partial monitoring. In Conference on Learning Theory, pages 21 1-2139. PMLR, 2019.
Tor Lattimore and Csaha Szepesvári. Bandit algorithms.. Cambridge University Press, 2020.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with baniibandit feedback. In Advances in Neural Information Processing Systems, pages 964-972, 2015.
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3260-3268, 2017.
Xiuyuan Lu and Benjamin Van Roy. Information-theorrticc confidence bounds for reinforcement learning. arXiv preprint arXiv:191 0.79444 2019.
Xiuyuan Lu, Benjamin Van Roy. Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen. Reinforcement learning, bit by bit. arXiv preprint arXiv:2103.04044 2021.
T. J. Mitchell and J. Beauchamp. Bayesian Variable Selection in Linear Regression. Journal of the American Statistical Association, 831404))1023-1032, 1988.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Saansity- lasso bandit. arXiv preprint arXi:: 2020.
Zhimei Ren and Zhengyuan Zhou. Dynamic batch learning in high-dimensional sparse linear contextual bandits. arXiv preprint 3Xii:2008.11911 2020.

---

Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22: 400-407, 1951.
Veronika Ročková and Edward George. The spike-and-slab lasso. Journal of the American Statistical Association, 113(521):431-444 2018.
Veronika Ročková and Edward I. George. EMVS: EM Approach to Bayesian variable selection. Journal of the American Statistical Association, 109(506):2288866 2014.
Mark Rudelson and Shuheng Zhou. Reconstruction from anisotropic random measurements. IEEE Transactions on Information Theory, 596))3333-3447, 2013.
Paat Rusmevichientonng and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
Daniel Russo and Beajamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, (9):)12221 122111211111111 2014.
Danicl Russo and Benjamin Van Roy. Learning optimize via cetemattioo-dircctoo sampling. Operations Research, 66(1):230-23) 2520052222222 2018.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizabilityy Available at SSRN, 2020.
R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58:267-222 288, 1996.
Roman Vershynin. On the role of sparsity compressed sensing and random matrix theory. In 2009 IEEE International Workshop Computational Advances in Multi- Adaptive Processing (CAMSAP), pages 189-192, 192. IEEE, 2009.
Xue Wang, Mingeheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high- dimensional covariates. In International Conference Machine Learning, pages 5200 5208, 2018.
Yining Wang, Yi Chen, Ethan Fang, Zhaoran Wang, and Runze Li. Nearly dimension -ineessiooniddeeeedeen sparse linear bandit small action spaces via best subset selection. arXiv preprint arXiv:2009.0000) 2020.
Yuhong Yang and Andrew Barron. information-thcoreticc determination of minimax of convergence. Annals of Statistics, pages 1564-1599, 1999.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
12

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "wNxS-9xrI2", "reviewer": "Reviewer_p7Zh", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and presents a theoretically sound method that tackles an important problem. It provides the first analysis using information theory for the sparse linear bandit problem. The result on the sub-optimality of optimism-based algorithms in sparse linear bandits is also nice.\n\nThe authors assume sparsity s is known but says (in Line 48) that this can be relaxed by putting a prior on it. I expect that a wrong prior on s can give a suboptimal result and the prior on s should be well-specified. I would like to ask the authors to elaborate on this.\n\nIn Lines 122-123, the authors argue that \"the confidence set can be constructed through an online-to-confidence set conversion approach [Abbasi-Yadkori et al., 2012]\" but can you construct the confidence set in a computationally efficient manner?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_5WY1ODZQgc", "reviewer": "Reviewer_jk2v", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[main]\n\nOriginality 5/5: new analysis and new algorithm\n\nQuality 4/5\n\nClarity 4/5: mostly clear\n\nSignificance 4/5: The algorithm would work well for small scale problems only. However, revealing the good property about IDS is important.\n\nI think the paper makes a solid contribution via the analysis of IDS for sparse parameters and proposing a computationally tractable algorithm.\n\nJust to make sure I understand the paper correctly, am I right that Theorem 5.3 works for any prior on \\Theta? Also, am I right that the model sampled from spike-and-slab prior is almost sparse but not actually sparse?\n\nQ: why assume the arms' L-\\infty norm is bounded, not L2 norm? What breaks down if we assume that the L2 norm of the arms is bounded?\n\nThe description of Algorithm 1 can be improved. Do you mean that we perform line 3-6 M times? Also, the thinning factor T is not well-explained. Also, how should I interpret the notation $\\theta^{(MT)}$?\n\n[etc]\n\n* I would increase the resolution of the figures and also enlarge the font sizes; currently, I have to zoom in like 800% to see details.\n* L253-254: \"the actions are drawn...\" => this can be deleted here because the authors discuss it in L274 again.\n* L278-279: I am not sure if I agree with \"ESTC performs better than non-sparsity-aware algorithms in the data-poor regime but perform poorly for the data-rich horizon.\". The first plot in Figure 3 is more data-rich than the third plot, yet it seems to perform still better than non-sparsity-aware algorithms at time=1000.\n* L489: \"Eq. (??)\" => missing reference.\n* L239-240: is $\\rho_i$ defined somewhere?\n\n----\n\n**after rebuttal**\n\nI am satisfied with the rebuttal.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. Please add some comments on its limitations and societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "no concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ZeEI3vzxcjQ", "reviewer": "Reviewer_rJi1", "summary": "The authors design and analyze an IDS-based algorithm for sparse linear bandits, showing its optimality in both the data-rich and data-poor regimes. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper nicely complements that of Hao et al. (2020) [NeurIPS] by deriving a Bayesian regret bound also in the data-rich regime. The authors show that their bound is almost optimal (up to log factors). This is nice. A neat implementation that ensure that IDS is computational efficient is also provided. One issue that is missing is whether there's also a corresponding regret bund for this computationally efficient variant of IDS. It would be good to discuss this. \n\nThe proofs look correct. \n\nThe experiments are convincing apart from the rightmost figure of Fig. 3 (for d = 100). Even though IDS outperforms all competitors, the regrets of all the algorithms, including IDS, seem to increase linearly. This suggests that the horizon is not large enough to see it tapering off. I suggest redoing this plot. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NIL ", "review_text": "", "extra_scores": {"ethical_concerns": "NIL ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "J2Aa2mcQUgq", "reviewer": "Reviewer_GQuz", "summary": "\nThis paper analyses information-directed sampling (IDS) for the problem\nof sparse linear bandits. They identify a key issue limiting\noptimism-based algorithms (or UCB type methods) where, for certain sparse\ninstances, the regret can scale nearly linearly in the time horizon.\nThey demonstrate that IDS does circumvents this information obstacle,\nby explicitly choosing actions that optimize for the information ratio:\ni.e. a ratio between the (sub)optimality of the action chosen and the\nfuture information gleaned from it. For IDS, they demonstrate an adaptive\nresult, that shows its (up to log factors) optimality in regret both \nfor short (data-poor) and long (data rich) time horizons. Computationally,\nIDS is non-trivial to implement in the sparse setting, for which the authors\npropose approach using mcmc sampling, borrowing from Bayesian sparse linear\nregression literature.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the paper: it's contributions are overall well-demarcated from the\nextensive literature on this and related problems, the paper provides a good high-level\nintroduction to the key obstacle and the proof technique they use. This is also a\ntopic that has traditionally been of significant interest to the community. I would recommend\nits acceptance to the NeurIPS program.\n\nMinor comments:\n\n1. In table 1 (and other places in text) perhaps put \\widetilde{O} to show that you are\nomitting log factors.\n2. Why does C_{min}(\\cal A) need to be >= 1 for the 'exploratory actions' condition? Is \n1 simply a convenient constant, e.g. does it suffice for it to be bounded away from 0?\n3. In principle, there could exist instances where the regret should scale\nas n^2/3 but where you do not have s-sparse optimal actions. For a lower bound \nthis does not matter since one needs only to demonstrate an example, but for\nthe achievability or upper bound, this matters. Can you comment on this: in particular, \ncan it be that even IDS is not adaptive to certain instances, where one does not\nhave the s-sparse optimal actions?\n4. Notation: probably better to use \\reals^{\\cal A} rather than \\reals^{|\\cal A|} and leave\nthe mapping implicit. \n5. Typos (likely not exhaustive): L.164: explore then *commit*, L.517: *Cauchy* Schwarz\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies sparse linear bandits in the Bayesian setting. Theoretically, it shows that information-directed sampling (IDS) has regret guarantees that adapt to (1) small/large action sets; (2) explorative action sets. Empirically, it gives a practical approximate implementation of IDS based on an empirical Bayesian approach. 

All reviewers are in consensus that this paper makes a solid contribution to a problem of good interest to the NeurIPS community. In the final version, please incorporate the reviewers' suggestion and re-run the experiments if necessary.
Decision: Accept (Spotlight)