Submodular Bandit Problem Under Multiple Constraints

Sho Takemori, Masahiro Sato, Takashi Sonoda, Janmajay Singh, Tomoko Ohkuma
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:191-200, 2020.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Submodular Bandit Problem Under Multiple Constraints %A Sho Takemori %A Masahiro Sato %A Takashi Sonoda %A Janmajay Singh %A Tomoko Ohkuma %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-takemori20a %I PMLR %P 191--200 %U https://proceedings.mlr.press/v124/takemori20a.html %V 124 %X 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.
APA
Takemori, S., Sato, M., Sonoda, T., Singh, J. & Ohkuma, T.. (2020). Submodular Bandit Problem Under Multiple Constraints. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:191-200 Available from https://proceedings.mlr.press/v124/takemori20a.html.

Related Material