High-Dimensional Sparse Linear Bandits
Stochastic linear bandits with high-dimensional sparse features are a practical model for a variety of domains, including personalized medicine and online advertising. We derive a novel $\Omega(n^{2/3})$ dimension-free minimax regret lower bound for sparse linear bandits in the data-poor regime where the horizon is smaller than the ambient dimension and where the feature vectors admit a well-conditioned exploration distribution. This is complemented by a nearly matching upper bound for an explore-then-commit algorithm showing that that $\Theta(n^{2/3})$ is the optimal rate in the data-poor regime. The results complement existing bounds for the data-rich regime and provide another example where carefully balancing the trade-off between information and regret is necessary. Finally, we prove a dimension-free $O(\sqrt{n})$ regret upper bound under an additional assumption on the magnitude of the signal for relevant features.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
We study the problem of dynamic batch learning in high-dimensional sparse linear contextual bandits, where a decision maker, under a given maximum-number-of-batch constraint and only able to observe rewards at the end of…
Decision MakingMarketingMulti-Armed BanditsVocal Bursts Intensity PredictionFLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits
High dimensional sparse linear bandits serve as an efficient model for sequential decision-making problems (e.g. personalized medicine), where high dimensional features (e.g. genomic data) on the users are available, but…
Decision MakingSequential Decision MakingThompson Sampling for High-Dimensional Sparse Linear Contextual Bandits
We consider the stochastic linear contextual bandit problem with high-dimensional features. We analyze the Thompson sampling algorithm using special classes of sparsity-inducing priors (e.g., spike-and-slab) to model the…
Multi-Armed BanditsThompson SamplingVariational InferenceVocal Bursts Intensity PredictionFixed-Budget Best-Arm Identification in Sparse Linear Bandits
We study the best-arm identification problem in sparse linear bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector $\theta^*$ may be of large dimension $d$, but only a few, say $s …
Information Directed Sampling for Sparse Linear Bandits
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…
Decision Making