A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits
Abstract
Many online learning applications adopt the stochastic bandit problem with a linear reward model, where the unknown parameter exhibits a succinct structure. We study minimax regret lower bounds which allow to know whether more efficient algorithms can be proposed. We introduce a general definition of succinctness and propose a novel framework for constructing minimax regret lower bounds based on an information-regret trade-off. When applied to entry-sparse vectors, our framework sharpens a recent lower bound by (Hao et al, NeurIPS 2020). We further apply our framework to derive novel results. To the best of our knowledge, we provide the first lower bounds for the group-sparse and low-rank matrix settings.
Cite
Text
Zeng and Honorio. "A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits." Advances in Neural Information Processing Systems, 2025.Markdown
[Zeng and Honorio. "A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/zeng2025neurips-novel/)BibTeX
@inproceedings{zeng2025neurips-novel,
title = {{A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits}},
author = {Zeng, Guo and Honorio, Jean},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/zeng2025neurips-novel/}
}