Submodular Bandit Problem Under Multiple Constraints
Sho Takemori, Masahiro Sato, Takashi Sonoda, Janmajay Singh, Tomoko Ohkuma
Abstract
The linear submodular bandit problemwas proposedto simultaneously address diversified retrieval and online learning in a recommender system.If there is no uncertainty, this problem is equivalent toa submodular maximization problem under a cardinality constraint.However, in some situations, recommendation lists should satisfyadditional constraints such as budget constraints,other than a cardinality constraint.Thus, motivated by diversified retrieval considering budget constraints,we introduce a submodular bandit problem under the intersection of$l$ knapsacks and a $k$-system constraint.Here $k$-system constraints forma very general class of constraints includingcardinality constraints and the intersection of $k$ matroid constraints.To solve this problem, we propose a non-greedy algorithm that adaptively focuses ona standard or modified upper-confidence bound.We provide a high-probability upper bound of an approximation regret,where the approximation ratio matches that of a fast offline algorithm.Moreover, we perform experimentsunder various combinations of constraints using asynthetic and two real-world datasetsand demonstrate that our proposed method outperforms the existing baselines.
BibTeX
@InProceedings{pmlr-v124-takemori20a,
title = {Submodular Bandit Problem Under Multiple Constraints},
author = {Takemori, Sho and Sato, Masahiro and Sonoda, Takashi and Singh, Janmajay and Ohkuma, Tomoko},
booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)},
pages = {191--200},
year = {2020},
editor = {Peters, Jonas and Sontag, David},
volume = {124},
series = {Proceedings of Machine Learning Research},
month = {03--06 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v124/takemori20a/takemori20a.pdf},
url = {https://proceedings.mlr.press/v124/takemori20a.html},
abstract = {The linear submodular bandit problemwas proposedto simultaneously address diversified retrieval and online learning in a recommender system.If there is no uncertainty, this problem is equivalent toa submodular maximization problem under a cardinality constraint.However, in some situations, recommendation lists should satisfyadditional constraints such as budget constraints,other than a cardinality constraint.Thus, motivated by diversified retrieval considering budget constraints,we introduce a submodular bandit problem under the intersection of$l$ knapsacks and a $k$-system constraint.Here $k$-system constraints forma very general class of constraints includingcardinality constraints and the intersection of $k$ matroid constraints.To solve this problem, we propose a non-greedy algorithm that adaptively focuses ona standard or modified upper-confidence bound.We provide a high-probability upper bound of an approximation regret,where the approximation ratio matches that of a fast offline algorithm.Moreover, we perform experimentsunder various combinations of constraints using asynthetic and two real-world datasetsand demonstrate that our proposed method outperforms the existing baselines.}
}