Worst-Case Regret Bounds for Combinatorial Bandits with Ranking Feedback

Combinatorial bandits with *ranking feedback* model a sequential decision-making problem in which the learner observes a *top-$m$* ranking of the set of $k$ arms played in each round. The setting has been examined under the lens of *top-$k$ regret minimization*, which accounts for the cost of pulling arms that are not among the best $k$. Existing works rely on the assumption that latent rankings are generated by a *Plackett-Luce* (PL) distribution and consider the special case of full-ranking feedback ($m = k$). They provide instance-dependent regret upper bounds which match the asymptotic logarithmic scaling in the learning horizon $T$, but suffer from a burn-in term which becomes $\Omega(T)$ for some choices of the PL parameters, preventing the derivation of sublinear worst-case bounds. In this work, we study the setting under the general top-$m$ feedback ($m \leq k$) and provide a worst-case regret lower bound of order $\Omega(\sqrt{T})$. Then, by introducing a novel algorithmic strategy, we derive an instance-dependent regret upper bound which does not suffer from the exploding burn-in term and a corresponding worst-case bound of order $\tilde{\mathcal{O}}(\sqrt{T})$, proving for the first time that it is possible to achieve sublinear worst-case regret w.r.t. the PL parameters. Moreover, we translate our algorithmic ideas to *multinomial logit* bandits, in which the learner receives *winner feedback* ($m = 1$) with non-zero probability of observing "no-choice". The existing regret bounds suffer from an exploding burn-in term, inversely proportional to the no-choice probability, that we avoid through our novel approach.