Sparse Optimistic Information Directed Sampling

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.

problem-dependent regret bound, which can be meaningful in the so-called data-poor regime, where d is much larger than T . Formally, we say that there exists an exploratory policy if the action set A is such that

which is equivalent to the condition that A spans R d . The exploratory policy is the distribution on A that achieves the maximum (which is guaranteed to exist when A is finite). The Explore the Sparsity Then Commit (ESTC) algorithm was shown to satisfy a regret bound of the order O(s 2/3 T 2/3 C -2/3 min ) [Hao et al., 2020]. The transition between the T 2/3 rate in the data-poor regime and the

T rate in the data-rich regime also appears in an existing lower bound of the order Ω(min(s et al., 2020].

Adapting to both regimes. Recently, Hao et al. [2021] showed that the sparse Information Directed Sampling (IDS) algorithm performs well in both regimes. Under the sparse optimal action condition (Definition 1), IDS satisfies a regret bound of the order O(min( √ dT ∆, (sT ) 2/3 ∆ 1/3 C -1/3 min )), where ∆ ∝ min(log(|A|), s log(dT /s)). This is simultaneously optimal in both the data-rich and data-poor regimes. However, this result is limited to the Bayesian setting. This is because IDS uses the Bayesian posterior to quantify uncertainty, which is only meaningful if θ 0 really is a random draw from the prior.