Linear Submodular Maximization with Bandit Feedback
<|reference_start|>Linear Submodular Maximization with Bandit Feedback: Submodular optimization with bandit feedback has recently been studied in a variety of contexts. In a number of real-world applications such as diversified recommender systems and data summarization, the submodular function exhibits additional linear structure. We consider developing approximation algorithms for the maximization of a submodular objective function $f:2^U\to\mathbb{R}_{\geq 0}$, where $f=\sum_{i=1}^dw_iF_{i}$. It is assumed that we have value oracle access to the functions $F_i$, but the coefficients $w_i$ are unknown, and $f$ can only be accessed via noisy queries. We develop algorithms for this setting inspired by adaptive allocation algorithms in the best-arm identification for linear bandit, with approximation guarantees arbitrarily close to the setting where we have value oracle access to $f$. Finally, we empirically demonstrate that our algorithms make vast improvements in terms of sample efficiency compared to algorithms that do not exploit the linear structure of $f$ on instances of move recommendation.<|reference_end|>
@article{chen2024linear,
    title={Linear Submodular Maximization with Bandit Feedback},
    author={Wenjing Chen, Victoria G. Crawford},
    journal={arXiv preprint arXiv:2407.02601},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.02601},
    primaryClass={cs.LG cs.DS}
}