InformationDirectedSamplingforSparseLinear Bandits

We develop a class of informationtheoretic Bayesian regret bounds that nearly match existing lower bounds on a variety ofproblem instances, demonstrating theadaptivity ofIDS. Toefficiently 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 regretreductions bysparseIDSrelativetoseveral baselines.