Sparse Optimistic Information Directed Sampling
This work addresses a key challenge in online decision-making for researchers and practitioners in machine learning, offering an incremental improvement by extending theoretical guarantees to worst-case settings.
The paper tackles the problem of achieving optimal worst-case regret in high-dimensional sparse linear bandits across both data-rich and data-poor regimes, and shows that Sparse Optimistic Information Directed Sampling (SOIDS) achieves this adaptivity without Bayesian assumptions, with empirical validation of its performance.
Many high-dimensional online decision-making problems can be modeled as stochastic sparse linear bandits. Most existing algorithms are designed to achieve optimal worst-case regret in either the data-rich regime, where polynomial dependence on the ambient dimension is unavoidable, or the data-poor regime, where dimension-independence is possible at the cost of worse dependence on the number of rounds. In contrast, the sparse Information Directed Sampling (IDS) algorithm satisfies a Bayesian regret bound that has the optimal rate in both regimes simultaneously. In this work, we explore the use of Sparse Optimistic Information Directed Sampling (SOIDS) to achieve the same adaptivity in the worst-case setting, without Bayesian assumptions. Through a novel analysis that enables the use of a time-dependent learning rate, we show that SOIDS can optimally balance information and regret. Our results extend the theoretical guarantees of IDS, providing the first algorithm that simultaneously achieves optimal worst-case regret in both the data-rich and data-poor regimes. We empirically demonstrate the good performance of SOIDS.