From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915811488169984 |
|---|---|
| author | Erez, Liad Koren, Tomer |
| author_facet | Erez, Liad Koren, Tomer |
| contents | 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 $s\ll 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 $\tilde{O}((poly(K/m)+sm/ε^2) \log(|Π|/δ))$ where $Π$ is the underlying (finite) class and $s$ is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever $s\ll 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 $Π$. 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((K^7+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(|Π|+\sqrt{smT\log |Π|})$, extending the result of Erez et al. (2024) who consider the simpler single label classification setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09257 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards Erez, Liad Koren, Tomer Machine Learning Artificial Intelligence 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 $s\ll 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 $\tilde{O}((poly(K/m)+sm/ε^2) \log(|Π|/δ))$ where $Π$ is the underlying (finite) class and $s$ is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever $s\ll 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 $Π$. 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((K^7+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(|Π|+\sqrt{smT\log |Π|})$, extending the result of Erez et al. (2024) who consider the simpler single label classification setting. |
| title | From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2502.09257 |