A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits

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 us 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 vector, our framework sharpens a recent lower bound by [7]. 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.

Prior Lower Bound Our Lower Bound

in Corollary 4.2 matrix in [12]