Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912119815929856 |
|---|---|
| author | Zhou, Julien Gaillard, Pierre Rahier, Thibaud Zenati, Houssam Arbel, Julyan |
| author_facet | Zhou, Julien Gaillard, Pierre Rahier, Thibaud Zenati, Houssam Arbel, Julyan |
| contents | We address the problem of stochastic combinatorial semi-bandits, where a player selects among P actions from the power set of a set containing d base items. Adaptivity to the problem's structure is essential in order to obtain optimal regret upper bounds. As estimating the coefficients of a covariance matrix can be manageable in practice, leveraging them should improve the regret. We design "optimistic" covariance-adaptive algorithms relying on online estimations of the covariance structure, called OLS-UCB-C and COS-V (only the variances for the latter). They both yields improved gap-free regret. Although COS-V can be slightly suboptimal, it improves on computational complexity by taking inspiration from ThompsonSampling approaches. It is the first sampling-based algorithm satisfying a T^1/2 gap-free regret (up to poly-logs). We also show that in some cases, our approach efficiently leverages the semi-bandit feedback and outperforms bandit feedback approaches, not only in exponential regimes where P >> d but also when P <= d, which is not covered by existing analyses. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15171 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits Zhou, Julien Gaillard, Pierre Rahier, Thibaud Zenati, Houssam Arbel, Julyan Machine Learning Statistics Theory We address the problem of stochastic combinatorial semi-bandits, where a player selects among P actions from the power set of a set containing d base items. Adaptivity to the problem's structure is essential in order to obtain optimal regret upper bounds. As estimating the coefficients of a covariance matrix can be manageable in practice, leveraging them should improve the regret. We design "optimistic" covariance-adaptive algorithms relying on online estimations of the covariance structure, called OLS-UCB-C and COS-V (only the variances for the latter). They both yields improved gap-free regret. Although COS-V can be slightly suboptimal, it improves on computational complexity by taking inspiration from ThompsonSampling approaches. It is the first sampling-based algorithm satisfying a T^1/2 gap-free regret (up to poly-logs). We also show that in some cases, our approach efficiently leverages the semi-bandit feedback and outperforms bandit feedback approaches, not only in exponential regimes where P >> d but also when P <= d, which is not covered by existing analyses. |
| title | Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits |
| topic | Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2402.15171 |