From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards

We study the problem of contextual combinatorial semi-bandits, where input contexts are mapped into subsets of size m of a collection of K possible actions. In each round, the learner observes the realized reward of the predicted actions. Motivated by prototypical applications of contextual bandits, we focus on the s-sparse regime where we assume that the sum of rewards is bounded by some value sll K. For example, in recommendation systems the number of products purchased by any customer is significantly smaller than the total number of available products. Our main result is for the (ε,δ)-PAC variant of the problem for which we design an algorithm that returns an ε-optimal policy with high probability using a sample complexity of tildeO((poly(K/m)+sm/ε2) log(|Pi|/δ)) where Pi is the underlying (finite) class and s is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever sll K, and in the regime where s=O(1), the leading term is independent of K. Our algorithm is also computationally efficient given access to an ERM oracle for Pi. Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors. In the special case of single-label classification corresponding to s=m=1, we prove an O((K7+1/ε2)log(|H|/δ)) sample complexity bound, which improves upon recent results in this scenario. Additionally, we consider the regret minimization setting where data can be generated adversarially, and establish a regret bound of tilde O(|Pi|+√smTlog |Pi|), extending the result of Erez et al. (2024) who consider the simpler single label classification setting.