Stochastic $k$-Submodular Bandits with Full Bandit Feedback
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916524918308864 |
|---|---|
| author | Nie, Guanyu Aggarwal, Vaneet Quinn, Christopher John |
| author_facet | Nie, Guanyu Aggarwal, Vaneet Quinn, Christopher John |
| contents | In this paper, we present the first sublinear $α$-regret bounds for online $k$-submodular optimization problems with full-bandit feedback, where $α$ is a corresponding offline approximation ratio. Specifically, we propose online algorithms for multiple $k$-submodular stochastic combinatorial multi-armed bandit problems, including (i) monotone functions and individual size constraints, (ii) monotone functions with matroid constraints, (iii) non-monotone functions with matroid constraints, (iv) non-monotone functions without constraints, and (v) monotone functions without constraints. We transform approximation algorithms for offline $k$-submodular maximization problems into online algorithms through the offline-to-online framework proposed by Nie et al. (2023a). A key contribution of our work is analyzing the robustness of the offline algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10682 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stochastic $k$-Submodular Bandits with Full Bandit Feedback Nie, Guanyu Aggarwal, Vaneet Quinn, Christopher John Machine Learning Data Structures and Algorithms In this paper, we present the first sublinear $α$-regret bounds for online $k$-submodular optimization problems with full-bandit feedback, where $α$ is a corresponding offline approximation ratio. Specifically, we propose online algorithms for multiple $k$-submodular stochastic combinatorial multi-armed bandit problems, including (i) monotone functions and individual size constraints, (ii) monotone functions with matroid constraints, (iii) non-monotone functions with matroid constraints, (iv) non-monotone functions without constraints, and (v) monotone functions without constraints. We transform approximation algorithms for offline $k$-submodular maximization problems into online algorithms through the offline-to-online framework proposed by Nie et al. (2023a). A key contribution of our work is analyzing the robustness of the offline algorithms. |
| title | Stochastic $k$-Submodular Bandits with Full Bandit Feedback |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.10682 |