Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
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_ | 1866909488843325440 |
|---|---|
| author | Zhou, Julien Gaillard, Pierre Rahier, Thibaud Arbel, Julyan |
| author_facet | Zhou, Julien Gaillard, Pierre Rahier, Thibaud Arbel, Julyan |
| contents | We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a non monotone submodular function taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a $O(d\log(dT))$ problem-dependent upper bound for the $1/2$-approximate pseudo-regret, as well as a $O(dT^{2/3}\log(dT)^{1/3})$ problem-free one at the same time, outperforming existing approaches. In particular, we introduce a problem-dependent notion of hardness characterizing the transition between logarithmic and polynomial regime for the upper bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08578 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit Zhou, Julien Gaillard, Pierre Rahier, Thibaud Arbel, Julyan Machine Learning Combinatorics Optimization and Control We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a non monotone submodular function taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a $O(d\log(dT))$ problem-dependent upper bound for the $1/2$-approximate pseudo-regret, as well as a $O(dT^{2/3}\log(dT)^{1/3})$ problem-free one at the same time, outperforming existing approaches. In particular, we introduce a problem-dependent notion of hardness characterizing the transition between logarithmic and polynomial regime for the upper bounds. |
| title | Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit |
| topic | Machine Learning Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2410.08578 |