Information Directed Sampling for Sparse Linear Bandits
This work addresses efficient decision-making in high-dimensional sparse bandit problems, offering an adaptive method with strong theoretical guarantees, though it is incremental as it builds on existing IDS frameworks.
The paper tackled the problem of high-dimensional online decision-making in stochastic sparse linear bandits by using information-directed sampling (IDS) to balance information-regret trade-offs, achieving Bayesian regret bounds that nearly match lower bounds and showing significant regret reductions in numerical results.
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.