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.
Introduction
In the linear bandit problem, an agent repeatedly chooses actions—represented by feature vectors—to maximize cumulative rewards. The reward for an action is the inner product of its feature vector and an unknown parameter vector $\theta^*$. In modern high-dimensional applications, the number of features $d$ often exceeds the number of observations. However, these problems are frequently tractable because $\theta^*$ is sparse, meaning only a small number $s \ll d$ of entries are non-zero.
The fundamental challenge lies in the exploration-exploitation trade-off: should the agent choose the action that currently appears best (exploitation), or an action that might reveal more about $\theta^*$ (exploration)?
The Limitations of Optimism
Most standard approaches, such as LinUCB, rely on the "optimism in the face of uncertainty" principle. These algorithms select actions that maximize the upper bound of a confidence interval. While effective in many scenarios, this paper demonstrates a critical failure mode: in "data-poor" regimes—where the time horizon is short relative to the dimension—optimistic methods are often too greedy. They may refuse to take actions that are slightly sub-optimal in the short term but highly informative, leading to linear regret.
Sparse Information-Directed Sampling (IDS)
To address these limitations, the authors propose Sparse Information-Directed Sampling (IDS). Rather than relying on optimism, IDS minimizes an information ratio: $$\Psi_t(a) = \frac{\Delta_t(a)^2}{g_t(a)}$$ where $\Delta_t(a)$ is the expected regret of action $a$ and $g_t(a)$ is the information gain about the optimal action. This objective explicitly treats information as a resource, allowing the agent to naturally decide when it is worth sacrificing immediate reward to gain critical knowledge about the environment's sparse structure.
Spike-and-Slab Prior and Empirical Bayes
A key component of the proposed method is the use of a hierarchical spike-and-slab Gaussian-Laplace prior. This prior is specifically designed for sparse settings: the "spike" (a Laplace distribution) encourages parameters to be near zero, while the "slab" (a Gaussian distribution) allows for precise estimation of the few non-zero parameters.
To make this computationally feasible, the authors develop an empirical Bayesian sampling algorithm that uses stochastic approximation to estimate the probability of each feature being "active," avoiding the heavy cost of full MCMC sampling.
Theoretical and Empirical Results
The authors establish new Bayesian regret bounds that demonstrate the adaptivity of IDS across different problem regimes. As shown in the comparison below, the derived rates for Sparse IDS nearly match known lower bounds across various action set types.
In simulations, Sparse IDS consistently outperforms baselines like LinUCB and standard Thompson Sampling. The advantage of the sparse prior becomes increasingly evident as the dimension $d$ grows. By effectively learning the sparsity pattern, the algorithm can focus its exploration on the relevant subspace much faster than non-sparsity-aware methods.
As illustrated in the posterior distribution histograms, the algorithm successfully concentrates its belief around the true parameter values (indicated by the red lines), effectively distinguishing between active and inactive features early in the learning process.
Conclusion
Information-Directed Sampling provides a robust framework for high-dimensional decision-making by quantifying the value of information. By combining IDS with a spike-and-slab prior, the authors provide a method that is both theoretically sound and empirically superior in sparse linear bandit problems. Future work includes extending this framework to contextual bandits and further optimizing the computational efficiency for extremely large action sets.
Summary updated