# Sparse Optimistic Information Directed Sampling

arXiv: https://arxiv.org/abs/2510.24234 · HTML: https://mlsanity.com/paper/2510.24234/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 28 Oct 2025.

## Builds on (most cited first, 23 of 23)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [First-Order Bayesian Regret Analysis of Thompson Sampling](https://mlsanity.com/paper/1902.00681/) (2019)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)

## Built on by (most cited first, 1 of 1)

- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)

## Abstract (arXiv)

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.